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

백준 웹사이트 "11053번 - 가장 긴 증가하는 부분 수열" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

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

---

소스 코드

#include <stdio.h>

int max(int a, int b);

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

    int LIS[N]; //LIS[i]: A[i]를 포함하는 가장 긴 부분 수열의 길이
    LIS[0]=1;  
    for(int i=1; i<N; i++){
        LIS[i]=1;
        for(int j=0; j<i; j++){
            if(A[i]>A[j]){
                LIS[i] = max(LIS[i], LIS[j]+1);
            }
        }
    }

    int max=0;
    for(int i=0; i<N; i++){
        if(LIS[i]>max)
            max=LIS[i];
    }
    printf("%d\n", max);
}

int max(int a, int b){
    if(a>b)
        return a;
    else
        return b;
}

---

문제 풀이

  LIS (Longest Increasing Subsequence), 즉 가장 긴 증가하는 부분수열을 구하는 문제입니다. 이는 이후 문제들에도 여러 번 응용되니, 확실하게 이해하는 편이 좋습니다.

  우선 Line 13에서 선언한 LIS 배열의 의미를 살펴봅시다. LIS[i]는 수열 A가 주어졌을 때 'A[i]를 포함하고, A[i]가 최대인 가장 긴 증가하는 부분수열의 길이'입니다. A[0]에서부터 A[i]까지 총 i+1개의 수만 고려했을 때, A[i]를 포함하는 가장 긴 증가하는 부분수열을 찾는 것이죠. 배열 LIS의 값들을 채우기 위해 동적 계획법이 사용됩니다.

  LIS[0]은 '(첫 번째 숫자) A[0]을 포함하고, A[0]이 최대인 가장 긴 증가하는 부분수열의 길이'이므로, 그 값은 당연히 A[0] 하나만 있을 경우로 1입니다.

  LIS[1]을 구할 때는 A[0]과 A[1]을 비교합니다. A[1]이 더 크다면, LIS[1]의 값은 LIS[0]+1 = 2가 되고, A[0]이 더 크다면 LIS[1]의 값은 1이 됩니다.

  이런 식으로, LIS[i]를 구할 때는 A[0] ~ A[i-1]을 각각 A[i]와 비교하고, 그 중 A[i]보다 작은 숫자가 있다면 (ex. A[j]) LIS[i]는 LIS[j]+1이 될 수 있습니다. LIS[j]를 이룬 수열의 끝에 A[i]를 더하면 조건을 만족하는 수열이 생기기 때문이죠. 이러한 LIS[j]+1은 LIS[i]가 될 수 있는 여러 후보 중 하나이고, 가능한 후보 중 가장 큰 값이 최종적인 LIS[i] 값이 됩니다.

  이와 같은 동적 계획법을 통해, LIS[0] ~ LIS[N]의 값을 모두 구할 수 있습니다. 이때, 최종 답은 LIS[N]이 아닐 수도 있습니다. 가장 긴 증가하는 부분수열이 항상 마지막 수를 포함한다고 할 수 없기 때문이죠. 따라서 LIS[0] ~ LIS[N] 중 최댓값을 구하면, 이는 수열 A의 가장 긴 증가하는 부분수열의 길이입니다.