(11053)(DP) 백준 가장 긴 증가하는 부분 수열

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

풀이

---

수열 중 가장 긴 증가하는 부분 수열을 구하면 된다.

arr[1] ... arr[n-1], arr[n]까지 총 n개의 수열이 주어진다고 할 때

dp[n] 을 이용해서 n번째 수열까지의 부분수열의 최대값을 저장하려고 한다.

1번째로 세워야할 조건

---

arr[n] > arr[n-1] 인가? 아니라면 증가하는 부분 수열이라고 할 수 없기 때문이다.

arr[i]를 마지막 배열이라고 가정 했을 때 수열의 최대 길이를 dp[i]라고 한다. 그러면  최대 dp[i]를 구하기 위해서 

arr[1], arr[2], arr[3] ... arr[i-1]까지 arr[i]보다 작은수가 존재하지 않는다면 dp[n]은 1이 될 것이다.

만약 arr[3]까지의 증가하는 부분수열의 최대길이인 dp[3]이 2라고 하고

arr[4]가 arr[3]의 값보다 크지 않다면 dp[4]는 2가 될것이다.

위의 조건과 예시를 종합해 조건식을 만들자면 아래와 같은 식이 나온다.

for(int i = 1; i <= N; i++){

for(int j = 1; j < i; j++}{

if(arr[j]< arr[i]) dp[i] = dp[j] + 1;

}

}

하지만 빠진 조건이 하나 존재한다. 우리는 부분수열의 최대길이를 구해야하지만  위의 식대로 프로그램을 돌리면 위의 조건문을 만족하는 i 와 가장 가까운 j 의 부분수열의 최대길이가 dp[i]에 대입되기 때문에 아래 예시와 같은 예외의 경우가 나타나게 된다.

ex) 

2    3    4    1    5

    dp[i]    1    2    3    1    ? <<-- dp[5]는 4가 되어야 하지만 dp[5] = dp[4] + 1; 로 인해 2가 되어 버릴 것이다. 그래서 아래와 같은 조건 하나를 추가한다.

if(dp[i] < dp[j] + 1) dp[i] = dp[j] +1;

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
#define Max(a,b) a>b ? a:b
 
 int main() {
    int N;
    int arr[1001] = { 0 };
    int dp[1001] = { 0 };
    int max = 0;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    
 
    for (int i = 1; i <= N; i++){
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (arr[i] > arr[j]) {
                if(dp[i] < dp[j] +1)    dp[i] = dp[j] + 1;
            }
        }
            max = Max(dp[i], max);
    }
    
    printf("%d", max);
 
    return 0;
 
}