[ DP - 11053 ] 가장 긴 증가하는 부분 수열(C++)

---

접근법

 

처음에는 0번째 부터 수열의 값을 체크 해 가면서 Max값을 다른 변수에 저장하고 해당 변수보다 큰 값이 있다면 Count를 1개씩 증가시키면서 변수를 Update하는 식으로 구현하였다. 너무 쉬운 감이 있었지만 역시 틀렸다.

 

10 20 5 12 17 30

 

다음과 같이 순열이 있다고 하자. 그러면 처음 접근법처럼 시도하면 Max = 10, Cnt =1일 것이다.

하나씩 주어진 순열과 비교 해 나가면, Max = 20, Cnt = 1이고 그 뒤로 5,12,17은 전부 20보다 작아서 Count 하지 않고, 마지막 30만 Count 되어서 Max = 30, Cnt = 3으로 가장 긴 증가하는 부분 수열의 길이는 3이 된다.

 

하지만 5, 12, 17, 30 이 더 긴 증가하는 부분 수열로, 길이는 4가 된다. 즉, 항상 0번째 순열의 위치부터 증가하는 순열이 존재한다고 생각하면 오산이다. 0번째 순열의 값이 더 크고, 뒤에서 더 작은 값부터 시작한다면, 잘못된 증가하는 순열을 추정할 가능성이 높다. 따라서 다른 접근법이 필요하다.

 

---

 

우리는 Dynamic Programming으로 접근해야 한다. 즉, 이전에 계산한 값을 사용해야 한다. 먼저 DP 배열을 전부 1로 초기화 하자. 일단은 자기 자신이 가장 긴 순열일 것이다. 

 

Arr[]	10	20	5	12	17	30
DP[]	1	1	1	1	1	1

 

인덱스 i,j를 활용하여 자기 자신보다 작은 숫자를 Count해서 비교하면 증가하는 순열을 찾을 수 있을 것이다. i는 기준이 되는 인덱스, j는 0부터 i보다 작은 범위에서 순열에 접근해 i index의 순열의 값과 비교해 보자. 

 

i가 0일 경우 자기 자신이라 1이다. i가 1일 경우 arr[i] = 20, j는 0이므로 arr[j] = 10이다. 따라서 DP[i]의 count를 1개 더해주면 된다. 

 

Arr[]	10	20	5	12	17	30
DP[]	1	2	1	1	1	1

 

그렇다면 i가 2일 경우 arr[2] = 5이기 때문에, j가 0,1에 접근 가능하지만 모두 5보다 크기 때문에 dp[i]는 변화가 없다. 

 

$$ if (arr[i] > arr[j]) \quad \to \quad DP[i] = DP[i] + 1 $$

 

단순히 위와 같은 Recursive Property로 해결 될 문제일까?

 

i가 3인 경우 arr[i] = 12이다. j는 0~2의 범위를 가지고 arr[0] = 10, arr[2] =5이기 때문에 DP[12]는 3이 된다. 하지만, 증가하는 순열은 10, 12 혹은 5, 12로 2이다. 단순히 증가시키는 것이 아니라, 자기 자신보다 작은 숫자를 가지는 인덱스의 DP 값에서 1을 증가시켜야지 증가하는 순열을 측정할 수 있다. 또한, 이미 확인된 증가하는 순열의 길이(DP[])가 더 클 수 있는 경우가 존재하므로 MAX()값을 추정해야 한다. 따라서 정확한 Recursive Property는 다음과 같다. 

 

$$ if (arr[i] > arr[j]) \quad \to \quad DP[i] = max(DP[j] + 1, DP[i]) $$

 

따라서 다음과 같이 측정할 수 있다.

 

Arr[]	10	20	5	12	17	30
DP[]	1	2	1	2	3	4

 

---

정답

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int DP[1001], arr[1001];

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int sum = 0;
    for (int i = 0; i < n; i++) {
        DP[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                DP[i] = max(DP[i], DP[j] + 1);
            }
        }
        sum = max(sum, DP[i]);
    }

    cout << sum;
    return 0;
}