가장 긴 증가하는 부분 수열 4

작성일 | In

[백준] 14002번 - 가장 긴 증가하는 부분 수열 4

문제 링크

가장 긴 증가하는 부분 수열 시리즈 중 LIS의 각 원소까지 출력하는 문제이다. 인덱스를 추적하는 방법을 떠올렸는데, 이분 탐색 방법으로는 구현하는데 어려움을 느껴 동적 계획법 + 인덱스 추적하는 방법으로 문제를 풀었다. 동적 계획법을 사용한 LIS 길이 구하는 풀이는 아래 포스트에서 다루었다. LIS의 동적 계획법 풀이에 대한 자세한 설명을 보고 싶다면 아래 포스트를 참고하면 되겠다.
[Algorithm] 최장 증가 부분 수열 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

int dp[1000];
int seq[1000];
int trace[1000];
int n;

int solve(int start) {
    int& ret = dp[start];
    if(ret == 0) {
        for(int i=start + 1; i<n; ++i) {
            if(seq[i] > seq[start]) {
                int res = solve(i);
                if(ret < res + 1) {
                    ret = res + 1;
                    trace[start] = i;
                }
            }
        }
        if(ret == 0)
            ret = 1;
    }
    return ret;
}

int main(void) {
    scanf("%d", &n);
    for(int i=0; i<n; ++i) scanf("%d", &seq[i]);

    for(int i=0; i<n; ++i)
        trace[i] = -1;

    for(int i=0; i<n; ++i)
        solve(i);

    int maxVal = 0, sIndex;
    for(int i=0; i<n; ++i) {
        if(maxVal <= dp[i]) {
            maxVal = dp[i];
            sIndex = i;
        }
    }    

    printf("%d\n", maxVal);
    while(trace[sIndex] > 0) {
        printf("%d ", seq[sIndex]);
        sIndex = trace[sIndex];
    }
    printf("%d", seq[sIndex]);
}

trace 배열이 인덱스를 추적하는데 쓰인다. 추적 인덱스는 dp배열의 값이 바뀔 때마다 갱신해주면 된다.
dp배열에서 최대값을 찾을 때 maxVal이 dp[i]보다 작거나 같을 때 갱신하도록 했다. 만약 작을 때만 갱신한다면 주어진 수열이 {5,6,1,2,3,4} 와 같을 때 문제가 생길 수 있다. 이 경우 dp[0], dp[1], dp[2] 가 모두 4일 것이고, 갱신 후 maxVal = 4, sIndex = 0이 되는데 trace[0] = 1, trace[1] = -1 이므로 원하는 LIS를 출력할 수 없다. 정확한 추적 시작 인덱스를 찾아내야 하므로 작거나 같을 때 갱신해야 한다.

0%