[백준/11053] 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)

1. 문제

 

 

2. 문제 풀이

 

다이나믹 프로그래밍(DP)의 대표적인 유형 중 하나인 LIS 문제이다.

현재의 상태를 지속적으로 저장시켜서 문제를 푸는 DP의 특성을 이용하여 문제에 접근한다.

나의 경우에는 다음과 같은 방법을 고안했다.

 

각 값들에 대해서, 그 값까지 만들어지는 LIS를 지속적으로 저장시켜 나간다.

이 때, 현재의 LIS를 구하는 방법은 다음과 같다.

'자신보다 작은 이전의 Value들에 대해서, 그때까지의 LIS가 가장 큰 값에 1을 더한다.'

 

즉, 각 LIS 값은 다음과 같은 조건으로 구한다.

 

(1) 현재 LIS 값보다 이전의 값들에 대해서

(2) 현재 자신의 Value보다 작은 값들에 대해서

(3) LIS 값이 가장 큰 값을 구한 후, 그 값에 1을 더한 값으로 구한다.

(4) 만약 조건에 해당하는 값들이 없다면, 해당 LIS는 1이다.

 

이와 같은 과정을 반복하면 다음과 같이 상태가 변경된다.

 

 

 

3. 코드 (C++)

 

#include <iostream>

using namespace std;

int main(void)
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, maxLIS = 1;
	cin >> N;

	int arr[1000][2] = { 0 };

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

	for (int i = 1; i < N; i++)
	{
		int maxSeq = -1;
		for (int j = 0; j < i; j++)
		{
			if (maxSeq < arr[j][1] && arr[i][0] > arr[j][0])
			{
				maxSeq = arr[j][1];
			}
		}
		if (maxSeq != -1)
		{
			arr[i][1] = maxSeq + 1;
			if (maxLIS < maxSeq + 1) maxLIS = maxSeq + 1;
		}
	}

	cout << maxLIS << '\n';

	return 0;
}