말이 참 복잡하지만, 결국 한 상자에 들어갈 수 있는 가장 많은 상자의 수를 구하는 문제이다.
상자는 자신보다 번호가 큰 상자 어디든 들어갈 수 있기 때문에, 주의해야한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 연습장
{
internal class _1965_boj
{
public void boj_1965()
{
int N = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int[] dp = new int[N];
for (int i = 0; i < N; i++)
{
dp[i] = 1;
}
// int[] dp = Enumerable.Repeat(1, N).ToArray(); for (int i =1; i < N; i++)
{
for (int j = 0; j < i; j++)
{
if (arr[j] < arr[i])
dp[i] = Math.Max(1 + dp[j], dp[i]);
}
}
Console.WriteLine(dp.Max());
}
}
}
|
cs |
|
|
|
문제를 보고 이해가 너무 안가서 코파일럿의 도움을 받아 간신히 이해를 했다.
코드 자체는 막힘없이 쉽게 써졌고, 예제는 전무 맞았으나 체점에는 틀렸습니다가 계속 나왔다.
알고보니 처음에 나는 dp의 0번지에만 1을 넣었는데, 이것은 0번 박스가 반드시 포함이 된다는 가정하에 작성되는 코드였다.
박스가 몇번지에 있든 가장 중첩이 많이된 박스의 중첩 수를 출력하는 것이므로 모든 배열의 원소를 1로 초기화하고 진행했더니 정답이었다.
'다이나믹 프로그래밍 한접시' 카테고리의 다른 글
| [백준] 14501번: 퇴사 [C#] (0) | 2024.04.14 |
|---|---|
| [백준] 2133번: 타일 채우기 [C#] (0) | 2024.04.13 |
| [백준] 1890번: 점프 [C#] (0) | 2024.04.10 |
| [백준] 2294번: 동전 2 [C#] (0) | 2024.04.09 |
| [백준] 9461번: 파도반 수열 [C#] (0) | 2024.04.09 |