[C++] 백준 1965번 - 상자 넣기

문제를 잘 곱씹어보면 아이디어가 하나 떠올랐는데, 백준 문제의 '가장 긴 증가하는 부분 수열' 이 떠올랐다. 생각해보면 이 아이디어가 Correct하게 맞아떨어지는데, 이는 해당 구간에서 오름차순으로 증가하는 수열이 결국 이 문제의 상자와 같기 때문이다. 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n;
int dp[1001];
int arr[1001];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	int ans = -1;
	
	for (int i = 1; i <= n; i++) {
		dp[i] = 0;
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		ans = max(ans, dp[i]);
	}

	cout << ans << endl;

	return 0;
}