다이내믹 가장 긴 감소하는 부분 수열-백준 11053번

가장 긴 감소하는 부분 수열

시간 제한 / 메모리 제한 / 제출 / 정답 / 맞힌 사람 / 정답 비율

문제

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

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

입력

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

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

출력

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

예제 입력 1

6
10 30 10 20 20 10

예제 출력 1

3

출처

문제를 만든 사람: baekjoon

비슷한 문제

• 11053번. 가장 긴 증가하는 부분 수열
• 11054번. 가장 긴 바이토닉 부분 수열
• 11055번. 가장 큰 증가하는 부분 수열
• 12015번. 가장 긴 증가하는 부분 수열 2
• 12738번. 가장 긴 증가하는 부분 수열 3
• 14002번. 가장 긴 증가하는 부분 수열 4
• 14003번. 가장 긴 증가하는 부분 수열 5

알고리즘 분류

• 다이나믹 프로그래밍

풀이

이것은 간단한 원리로 구현을 할 수 있다.

• 각 인덱스를 순회를 돈다
  • 현재 인덱스보다 이전에 놓여있으면서 그 값이 지금 인덱스보다 크면 길이를 1 증가

최종적으로 나온 길이들 중 최댓값을 찾고, 1을 더하며 바로 정답이다. 1을 더하는 까닭은 입력이 없는 경우가 문제에서 없으니 길이가 0인 경우가 없기 때문이다. 여기까지의 모든 설명을 보면 가장 긴 증가하는 부분 수열과의 차이는 값이 지금 인덱스보다 클 때, 작을 때 조건 방향일 뿐이다. 이것과 정확히 같은 방식으로 하되 부등호만 바꾸면 백준 상자넣기나 가장 긴 증가하는 부분 수열을 풀 수 있다. 그러나 가장 긴 증가하는 부분수열 2와 같은 것은 DP가 아닌 이분탐색을 이용하기 때문에 풀 수 없다.

코드

#include <stdio.h>
#include <stdlib.h>

#define MAX(x, y) ((x) > (y)) ? (x):(y)

int main() {
    int N;
    scanf("%d", &N);
    int *A  = calloc(N, sizeof(int));
    int *DP = calloc(N, sizeof(int));

    for(int i = 0; i < N; i++) scanf("%d", A + i);

    for(int k = 0; k < N; k++) {
        for(int i = 0; i < k; i++) {
            if(A[i] > A[k]) DP[k] = MAX(DP[i] + 1, DP[k]);
        }
    }
    int result = 0;
    for(int i = 0; i < N; i++) {
        result = MAX(result, DP[i]);

    }

    result++; // minimum: 1
    printf("%d", result);
    return 0;

}