[백준] 11722번: 가장 긴 감소하는 부분 수열 - C++

문제

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

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

 

입력

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

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

 

출력

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

 

---

DP를 이용하여 풀 수 있는 문제.

사실상 11053번 가장 긴 증가하는 부분 수열 문제에서 괄호만 바꾸면 풀 수 있는 문제이다. 설명은 링크 참조.

 

접근 방식은 다음과 같다.

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에 저장.

 

코드

#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;
}