백준 1965번 상자넣기

https://www.acmicpc.net/problem/1965

이번 문제를 풀 땐 n번째 마다 최대로 넣을 수 있는 상자를 계산하는 것으로 점화식을 구성하였다.

즉, num[n] = n번째에서 가장 최대로 넣을 수 있는 상자의 수 가 된다.

이것을 기준으로, n번째 상자에 왔을 때 (n-1, n-2, n-3, ... 1)번째 상자를 탐색하면서

n번째 상자가 n-1번째 상자보다 크면, num[n]을 비교하여 최대값을 갱신해주면 된다.

그리고 처음에 num[n] = 1 로 초기화 시켜준 것은 상자의 배열이 9 8 7 6 5 라면 답은 1이기 때문이다.

(간단하게 말하면, 어느 자리에서든 상자에 최소 1개를 넣을 수 있다는 뜻이다.)

#include <cstdio>
#include <algorithm>
#define MAX 1000
using namespace std;
int box[MAX + 1] = { 0, };
int num[MAX + 1] = { 0, };
int N;
int main()
{
	int result = 0;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		num[i] = 1;
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &box[i]);
		int maxNum = 0;
		for (int j = i - 1; j >= 1; j--)
		{
			if (box[i] > box[j] )
			{
				maxNum = max(num[j], maxNum);
				num[i] = maxNum + 1;
			}
		}
	}
	for (int i = 1; i <= N; i++)
	{
		result = max(num[i], result);
	}
	printf("%d\n", result);
	return 0;
}