[현대 소프티어] (C++) 징검다리

정답률 28%의 문제이다.

가장 긴 증가 부분순열을 구하는 문제이다.

DP를 사용하여 푸는 흔한 문제이며 어렵지 않게 풀었다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N; cin >> N;
	vector<int> arr(N, 0);
	vector<int> cnt(N, 1);

	for(int i = 0; i < N; i++)
		cin >> arr[i];

	for(int i = 0; i < N; i++)
	{
		for(int j = i + 1; j < N; j++)
			if(arr[i] < arr[j] && cnt[j] <= cnt[i])
			{
				cnt[j] = cnt[i] + 1;
			}
	}

	int max_val = *max_element(cnt.begin(), cnt.end());

	cout << max_val << '\n';

	return 0;
}