[백준] 1965번 상자넣기

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

1965번: 상자넣기

그냥 LIS(Longest Increasing Sequence)를 구하면 된다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> boxes(n);
	for (int i = 0; i < n; i++) {
		cin >> boxes[i];
	}
	int maxBox = 0;
	vector<int> dp(n);
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		int maxDp = 0;
		for (int j = 0; j < i; j++) {
			if (dp[j] > maxDp && boxes[j] < boxes[i]) {
				maxDp = dp[j];
			}
		}
		dp[i] = maxDp + 1;
		if (dp[i] > maxBox)
			maxBox = dp[i];
	}
	cout << maxBox;
	return 0;
}