[C/C++] 백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS)

 

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;

int n, tmp;
int A[1001];
int DP[1001];

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{	
		cin >> A[i];
		tmp = 0; // 가장 큰 tmp값을 찾기위해 0으로 초기화
		for (int j = 0; j < i; j++)
		{
			// 현재값(A[i])보다 작은 이전값들(A[j])중에서
			// 가장 큰 DP[j]값을 구하고 그 값을 tmp에 저장
			if (A[i] > A[j] && DP[j] > tmp) tmp = DP[j];
		}
		DP[i] = tmp + 1; // 현재 수열 길이 +1 증가
	}

	sort(DP, DP + n, greater<>()); // 내림차순 정렬

	cout << DP[0]; // 최대값 출력

}

 

먼저 n개의 원소를 가진 수열 A가 있고 k번째의 DP값을 정할 때를 살펴보면

A[0]	A[1]	...	A[k]	...	A[n-2]	A[n-1]
DP[0]	DP[1]	...	DP[k]	...	DP[n-2]	DP[n-1]

 

이 문제 풀이의 핵심인 k번째 입장에서 DP값을 결정하기 가장 좋은 선택은

• 현재 값 A[k]보다 작은 (0~k-1) 번째 A값들 중에서
• DP값이 가장 큰 값을 선택하고 그값에서 +1을 해준 값을 DP[k]값으로 결정하는 것이다.

 

이러한 알고리즘을 통해 LIS를 쉽게 구할 수 있게 된다.

 

입력 예제 1로 예를 들자면

INDEX	0	1	2	3	4	5
A	10	20	10	30	20	50
DP	1	2	1	?	.	.

앞부분을 생략하고, 현재 DP[3]의 값을 결정해야 하는데 A[0], A[1], A[2] 중에서 A[3] = 30 보다 작은 값의 인덱스 중에서 DP값이 가장 큰 것을 선택하면(DP[1] = 2로 가장 큽니다) DP[3] 은 2에서 +1을 해준 3으로 결정된다.

 

INDEX	0	1	2	3	4	5
A	10	20	10	30	20	50
DP	1	2	1	3	?	.

DP[4]도 마찬가지이다. A[3]의 경우 30으로 A[4] = 20 보다 값이 크기 때문에 제외되고 A[4]보다 작은 A[0], A[1], A[2]의 인덱스들 중에서 DP[1] = 2로 가장 크기 때문에 DP[4] 는 2에서 +1을 해준 3으로 결정된다.

 

INDEX	0	1	2	3	4	5
A	10	20	10	30	20	50
DP	1	2	1	3	3	?

DP[5]의 값은 A[5] = 50이고 이 값은 A[0~4]보다 크므로 인덱스 0~4 사이에서 가장 큰 DP값인 3 + 1 = 4로 결정된다. 

INDEX	0	1	2	3	4	5
A	10	20	10	30	20	50
DP	1	2	1	3	3	4

 

그리고 sorting을 통해 가장 큰 DP값을 출력해주면 정답!

 

 

www.acmicpc.net/problem/11053

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