[BOJ] 백준 11053 가장 긴 증가하는 부분 수열

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

 Input 

6

10 20 10 30 20 50

 

 Output 

4

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

LIS (Longest Increasing Subsequence)

subsequence은 연속하지 않아도 되는 부분 수열입니다.

따라서 subsequence의 개수는 N2 입니다.

완전 탐색 방법으로 접근할 경우 TLE 발생

 

해당 문제는 DP로 풀 수 있습니다.

dp[i] = i번째 원소를 부분 수열의 마지막으로 하는 수열 중 가장 긴 수열의 길이로 정의

arr[] 배열에서 1 ~ i-1까지 arr[i]보다 작은 원소를 찾습니다.

찾은 arr[j]와 매칭되는 DP[j] 값을 탐색과정에서 찾은 DP값들과 비교하여

가장 큰 DP[j]인 val을 구합니다. → DP[i] = val + 1

 

시뮬레이션

① arr[] =

    DP[] = {} ← 시작 인덱스를 1로 해서 DP[0] = 0으로 설정

    0~1-0까지 가장 큰 DP[] = 0 이므로 DP[1] = 0 + 1 = 1

② arr[] =

     DP[] =

    →10 < 20 이므로 DP[1] = 1 → val = 1 

     ▶ DP[2] = val + 1 = 1 + 1 = 2

③ arr[] =

     DP[] =

     → 10 == 10 이므로 val 변화 X

     → 20 > 10 이므로 val 변화 X

     ▶ DP[3] = val + 1 = 0 + 1 = 1

④ arr[] =

     DP[] =

     → 10 < 30 이므로 DP[1] = 1 → val = 1

     → 20 < 30 이므로 DP[2] = 2 → val < 2 → val = 2

     → 10 < 30 이므로 DP[3] = 1 → val > 1 → val = 2 로 유지

     ▶ DP[3] = val + 1 = 2 + 1 = 3    

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
inline int max(int A, int B) { return A > B ? A : B; }
int N, ans, DP[1010], arr[1010];
 
int main(void) {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d", &arr[i]);
 
    int i, j, val;
 
    for (i = 1; i <= N; ++i){
        val = 0;
        for (j = 0; j < i; ++j) {
            if (arr[j] < arr[i]) {
                val = max(val, DP[j]);
            }
        }
        DP[i] = val + 1;
 
        // ans = DP[i] 중 최대값
        ans = max(ans, DP[i]);
    }
 
    printf("%d\n", ans);
}