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

문제 위치 : https://www.acmicpc.net/problem/11568

---

1. Approach

 

(1) LIS( Longest Increasing Sequence) 로 접근한다.

 

-> LIS는 다이나믹 프로그래밍 문제 중에서도 대표적인 문제이자, 많이 사용되는 풀이 방법 중 하나이므로 정확히 이해하고 지나가는 것을 권장한다.

 

아래 링크에서 LIS 풀이 방법을 확인 할 수 있다.

https://blog.naver.com/lgh121546/221872278258

 

(2) DP 배열 정의

 

-> DP[idx] : idx까지 가장 긴 최장 증가 수열

 

 

2. Source Code

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXLEN 1000
using namespace std;
/*
	문제 설명

	1. 준민이가 앞의 카드부터 임의의 개수만큼 골라서 제시하는데, 제시한 카드의 수열이 증가가 아니면 놀림.
	2. 순증가 + 원소의 개수가 제일 많은 수열이어야 한다.

	ex) 8, 9 , 1, 2, 10 을 보여줬을 때

	( 8, 9, 10 ), ( 1, 2, 10 ) 이면 놀림받지 않지만
	( 8, 9 ), ( 1, 2 ) 면 놀림받을 것이다.

	결론,

	주어진 순열에서 원소가 순증가이며, 가장 큰 개수를 가진 것
	-> LIS ( Longest Increasing Sequence ) 문제로 풀 수 있다.
*/
int n;
int seq[MAXLEN + 1];
int dp[MAXLEN + 1];		// dp[idx] : idx 위치까지 조건에 만족하는 원소의 최대 길이

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> seq[i];
	
	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = 1; j <= i; j++)
		{
			if (seq[j] < seq[i] && dp[i] < dp[j] + 1)
			{
				dp[i] = dp[j] + 1;
			}
		}
	}

	cout << *max_element(dp + 1, dp + n + 1);
	
	return 0;
}