DP - LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)

관련 문제:

백준 11053번 - 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053

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

주어진 수열에서 가장 긴 증가하는 부분수열을 찾는 것이다. 예를 들어 {10, 20, 10, 30, 20, 50}의 LIS는 {10, 20, 30, 50}이다.

 

풀이:

DP(i) = i번째 원소를 반드시 맨 끝에 포함할 때 LIS의 길이

이 경우 DP(i) = max[ {DP(j) + 1 | j번째 원소 < i번째 원소} ,

                                1] 이다.

 

해설:

1) "{DP(j) + 1 | j번째 원소 < i번째 원소}"의 의미

i번째 원소를 반드시 맨 끝에 포함해야 하므로, 이 원소를 새로 포함시켜줄 부분수열의 마지막 원소는 i번째 원소보다 작아야 한다. 즉, j번째 원소 < i번째 원소인 조건을 만족해야 한다. 그리고, 조건을 만족하여 새로 구하게 된 부분수열의 길이는 j번째 원소까지 포함했을 때의 길이 + 새롭게 추가한 i번째 원소 이므로 DP(j) + 1이다. 이러한 모든 DP(j) + 1 값들의 집합이 DP(i)의 후보가 된다.

 

2) "1"의 의미

i번째 원소인 자기자신을 제외하면 어느것도 선택하지 않는 경우이다.

 

3) max( ... , ...)

이렇게 했을 때 "가능한 DP(j) + 1들"과 "1" 중 가장 큰 것이 DP(i)의 값이다.

 

Pseudocode:

N = 주어진 수열의 길이;
DP[N];                                               //DP[i]는 위의 설명에서 DP(i) 값을 의미함.

num[N];                                            //주어진 수열

for (i = 0 ~ N-1) {

    DP[i] = 1;
    for (j = 0 ~ i) {                                // max({DP(j) + 1 | j번째 원소 < i번째 원소})로 갱신하기
        if ((num[j] < num[i]) && (DP[j] + 1 > DP[i])) DP[i] = DP[j] + 1; 
    }
}

최대 길이 = max(DP[0 ~ N-1]);          //시간을 단축하려면 위의 반복문 안에서 최댓값을 갱신하는 것이 좋겠지?