[백준][11722번][DP] 가장 긴 감소하는 부분 수열

가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722

<코드>

#include <stdio.h>
 
int main(void){
    int N;
    int Dp[1010] = {};
    int A[1010] = {};
    int max = 0;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
        scanf("%d", &A[i]);
 
    for (int i = 1; i <= N; i++)
    {
        int min = 0;
        for (int j = 0; j < i; j++){
            if (A[i]<A[j]){
                if (min < Dp[j])
                    min = Dp[j];
            }
        }
        Dp[i] = min + 1;
        if (max < Dp[i])
            max = Dp[i];
    }
 
    printf("%d\n", max);
 
}

<문제 푼 요령>

1. 이 문제야 말로 '가장 긴 증가 하는 부분 수열' 문제와 동일하다. 

2. 다른 점은 증가하는 수열이 아닌 감소하는 수열이기 때문에 검색할 때의 조건이 자신보다 높은값만 찾으면 된다.