[백준] 1965번. 상자넣기 (C++)

문제

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

풀이

[LIS,DP]

코드

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

int main()
{
	//INPUT
	int N; cin >> N;
	vector<int> box(N);
	vector<int>dp(N, 1);
	for(int i=0;i<N;i++)
	{	cin >> box[i];	}

	//CHECK
	for (int i = 0; i < N; i++)
	{
		for (int k = 0; k < i; k++)
		{
			if(box[i]>box[k])dp[i] = max(dp[i], dp[k] + 1);
		}
	}
	//RESULT
	cout << *max_element(dp.begin(), dp.end());
}

 

동일한 문제

https://yun000.tistory.com/164

[백준] 11055번. 가장 큰 증가하는 부분 수열 (C++)