가장 긴 증가하는 부분 수열

작성일 | In

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

문제 링크

LIS를 동적 계획법을 이용하여 풀었다. 알고리즘에 대해서는 링크에 자세하게 다룬다.

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
#include <bits/stdc++.h>
using namespace std;


/*
    dp[k]에 담겨있는 값 : 인덱스 k부터 마지막 인덱스까지의 부분 수열 중 가장 길이가 긴 부분 수열의 길이
    seq : 주어진 수열
*/

int dp[1001];
int seq[1001];
int n;

// start 변수는 현재 seq에서의 인덱스를 의미한다.
int solve(int start) {
    int& ret = dp[start];
    // 갱신된 적이 없는 dp만 갱신한다.
    if(ret == 0) {
        for(int i=start + 1; i<=n; ++i) {
            // 현재 인덱스의 dp값보다 뒤 인덱스 dp값이 더 크다면, LIS 조건을 만족하므로 해당 인덱스로 이동한다.
            // 리턴받은 값 + 1이 현재 dp값보다 크다면, 갱신한다. 
            if(seq[i] > seq[start])
                ret = max(ret, solve(i) + 1);
        }
        // 현재 인덱스보다 뒤에 있는 모든 seq값이 더 작다면 ret는 갱신되지 않는다.
        // 이 경우, dp 값은 1이 된다.
        if(ret == 0)
            ret = 1;
    }
    return ret;
}

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

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

    // dp배열 내 어느 위치의 값이 가장 큰지 탐색한다.
    int maxVal = 0;
    for(int i=1; i<=n; ++i) {
        if(maxVal < dp[i])
            maxVal = dp[i];
    }
    printf("%d", maxVal);
}
0%