11053) 가장 긴 증가하는 부분 수열 (C++)

 출처 

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

11053번: 가장 긴 증가하는 부분 수열

 내 풀이 

#include<iostream>

using namespace std;

int DP[1001];	
int Num[1001];

int N = 0;
int result = 0;

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> Num[i];
	}
	
	//LIS 알고리즘으로 풀기 
	for (int i = 1; i <= N; i++)
	{
		int max = 0;
		for (int j = i; j >= 0; j--)
		{
			if (Num[i] > Num[j])
			{
				if (DP[j] >= max) max = DP[j];
			}
			DP[i] = max + 1;
		}
	}

	//최댓값 찾기 
	for (int i = 1; i <= N; i++)
	{
		if (DP[i] >= result) result = DP[i];
	}

	cout << result;
}

 해설

LIS 알고리즘을 적용시켜 풀어보았다. 

 

DP[i]를 Num[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이라고 하면 Num[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 Num[i]보다 작은 값이어야 한다. 따라서 Num[i]를 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는 A[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다. 

출처: 나무위키 

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

 

 

이를 바탕으로 현재 Num[i]값보다 작은 값들을 확인하여 가장 높은 DP의 값에 1을 더하여 DP[i]를 구한 뒤 

마지막에 가장 높은 DP값을 가진 값을 정답으로 출력하였다.

 

 느낀점 

LIS라는 새로운 알고리즘을 알게 되어서 좋았다.