[백준] 11053번 가장 긴 증가하는 부분 수열

1. Approach

 

(1) 다이나믹 프로그래밍으로 접근한다.

 

-> KOI 유전자가 될 수 있는 최대 길이를 문자열의 처음, 끝부터 분할해나가면서 확인한다.

 

(2) DP 배열 정의

 

-> dp[i] 는 i 번째 인덱스 까지의 배열 중 가장 긴 부분수열의 길이.

 

(3) 풀이 방법

 

-> 내부 for문을 1부터 j - 1 까지 돌리면서 a[j] < a[i] ( i 번째 인덱스 값이 더 크고 ) && dp[j] + 1 > dp[i] ( 현재 i 인덱스의 가장 긴 부분수열의 길이 보다 큰 경우에)

 

2. Source Code

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[1001];
int dp[1001];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	// 길이가 가장 길어야 한다.
	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = 1; j <= i; j++)
		{
			if (a[j] < a[i] && dp[i] < dp[j] + 1)
			{
				dp[i] = dp[j] + 1;
			}
		}
	}
	cout << *max_element(dp + 1, dp + n + 1);
	return 0;
}

3. 비슷한 문제

1. 가장 긴 증가하는 부분 수열 2, 3, 4, 5
2. 가장 긴 감소하는 부분 수열
3. 가장 긴 바이토닉 수열

4. 참조

---

www.acmicpc.net/problem/11053