[백준][11053번][DP] 가장 긴 증가 부분 수열

가장 긴 증가 부분 수열

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

<코드>

#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. 그래서 각 부분마다 과거의 저장한 배열을 검색을 해야한다. 쉽게 설명하자면 아래 그림과 같다. 

3. 그래서 여기서 다른점은 이 중에서 가장 긴 길이의 값을 뽑는 거기 때문에 각 길이에 대해서 최대값이 나오면 갱신해 줘야한다.