[ALGOSPOT] 알고스팟: Longest Increasing Sequence

https://www.algospot.com/judge/problem/read/LIS

algospot.com :: LIS

 

#include <bits/stdc++.h>
using namespace std;

int C, N, subseq[501], mx;
int dp[501];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> C;
	
	while(C--){
		memset(dp, 0, sizeof(dp));
		cin >> N;
		for(int i = 1; i <= N; i++){
			cin >> subseq[i];
		}
		
		dp[1] = 1;
		for(int i = 2; i <= N; i++){
			mx = 0;
			for(int j = 1; j < i; j++){
				if(subseq[j] < subseq[i] && dp[j] > mx) mx = dp[j];
			}
			dp[i] = mx + 1;
		}
		cout << *max_element(dp+1, dp+N+1) << '\n';
	}
}

 

위 풀이는 dp table을 다음과 같이 정의한 O(N^2) 알고리즘입니다.

dp[k] : 주어진 수열의 k번째 항을 마지막 항으로 포함하는 가장 긴 증가 부분 수열의 길이

table을 정의하면 점화식을 찾는 것은 쉽습니다.

k번째 항보다 앞선 항 중에 k번째 항보다 값이 작으면서 dp 값이 가장 큰 항을 선택한 후 

그 dp 값(길이)에 자신(k번째 항)을 포함한다는 의미에서 값을 1 더해주면 됩니다.

 

주의할 점

생각없이 풀다가 기껏 잘 풀어놓고 습관적으로 dp[N]을 출력하지 않도록 주의해야 합니다.

10 11 12 13 14 15 16 17 1 

N = 9인 위 수열을 예로 들면 LIS의 길이는 8입니다. dp[8] = 8, dp[9] = 1로 dp[9]를 출력하게 되면 오답을 출력하게 됩니다.

 

이 문제의 경우 주어지는 N이 최대 500이므로 O(N^2)으로 1초 내에 충분히 통과가 가능하지만,

만약 N이 10^6 으로 주어진다면 시간 초과가 나게 됩니다.

가장 긴 증가하는 부분 수열(Longest Increasing Sequence, 이하 LIS) 문제는 O(NlogN)에 해결이 가능합니다.

LIS의 길이만을 출력하는 것이 아니라 실제 LIS 중 하나를 출력하는 문제도 고민해야 합니다.

(LIS는 여러 개일 수 있으므로 백준 등에서 스페셜저지로 채점하게 됩니다.)

이는 추후 백준 LIS 문제 시리즈를 다루면서 정리해보겠습니다.