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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (1 ≤ A_i ≤ 1,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

DP를 이용하여 풀 수 있는 문제. 여태까지 풀었던 다른 DP문제들과 조금 다르게 접근해야돼서 어려웠던 문제같다. 검색해보니 이러한 문제 유형을 LIS(Longest Increasing Subsequence)라고 하더라

수열을 담을 배열 A와 증가하는 부분 수열의 길이를 기록할 배열 D를 선언한 후, A의 1번째 원소부터 점검을 한다. 자신(i)보다 이전에 있는 원소들과 비교해가며 작은 값이 존재할 경우 D에 있는 값을 비교해가며 가장 큰 값(최대 길이)을 D[i]에 대입한다. 이를 순서대로 정리하자면 다음과 같다.

 

1. A 배열 내에서 A[i]보다 작은 값을 찾는다. (1 ≤ i ≤ N, 1 ≤ j < i)

2. A[i]보다 작은 값인 원소의 위치를 j라고 할 때, 다음과 같은 경우를 고려하여 D[i]를 구한다.

        2-1. D[i] ≤ D[j], A[i]까지의 가장 긴 증가하는 부분 수열의 길이는 A[j]까지의 가장 긴 증가하는 부분 수열의 길이 D[j]에 A[i]를 포함하여 1을 더한 값이므로 D[i] = D[j] + 1

        2-2. D[i] > D[j], A[i]까지의 가장 긴 증가하는 부분 수열의 길이는 여전히 D[i] = D[i]

3. D[i]까지의 값 중 가장 큰 값(최대 길이)을 length에 저장.

 

여담으로 값 비교 부분에서 (memo[i] > memo[j] ? memo[i] : memo[j] + 1) 를 (memo[i] > memo[j] ? memo[i] : memo[i] + 1)로 썼는데 답이 통과됐었다. ..왜그런지 잘 모르겠다.

코드

#include <cstdio>
#define MAX 1001

int DP(int num);

int main(void) {
    int n;
    scanf("%d", &n);
    printf("%d\n", DP(n));
    return 0;
}

int DP(int num) {
    int A[MAX] = { 0 };
    int memo[MAX] = { 0 };
    int length = 0;

    for(int i = 1; i <= num; i++) {
        scanf("%d", &A[i]);
    }

    for(int i = 1; i <= num; i++) {
        memo[i] = 1;
        for(int j = 1; j < i; j++) {
            if(A[i] > A[j]) {
                memo[i] = (memo[i] > memo[j] ? memo[i] : memo[j] + 1);
            }
        }
        length = (length > memo[i] ? length : memo[i]);
    }

    return length;
}