[C++] 백준 11568번: 민균이의 계략

문제 링크

11568번: 민균이의 계략

문제 요약

민균이의 카드가 주어진다. 카드에 쓰인 숫자가 증가하도록, 최대의 카드를 뽑았을 때 이 카드의 수를 구해야 한다.

접근 방법

가장 긴 증가하는 부분 수열(Longest Increasing Subsequence) 기본 문제와 사실상 거의 동일합니다. N이 최대 1000이기 때문에 $O(N^2)$ 풀이로도 통과할 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;


int arr[1000], dp[1000];

int main(void)
{
	int n;
	cin >> n;

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

	int res = dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1;
		
		for (int j = 0; j < i; j++)
		{
			if (arr[i] > arr[j] && dp[j] + 1 > dp[i])
				dp[i] = dp[j] + 1;
		}

		res = max(res, dp[i]);
	}

	cout << res;
	return 0;
}