[백준]11053-가장 긴 증가하는 부분 수열(Dynamic Programming)

이 문제 역시 동적 계획법으로 푸는 문제다.

주어진 수열에서 일정 부분을 뽑아 가장 긴 증가수열을 만들고, 그 길이를 구하는 문제다.

 

이 문제에는 가장 심플한 규칙이 있다.

v[i][0]이 i번째 수의 값이고, v[i][1]이 i번째 수의 값을 증가수열의 마지막 수로 잡았을 경우 가장 길게 만들 수 있는 증가수열의 길이라고 한다면,

v[i][0]<v[j][0] (조건 = j > i)라면 v[i][1] < v[j][1]이다.

이 말이 무슨 말이냐면, 주어진 수열의 어떠한 값이 그보다 왼쪽에 있는 수열보다 크다면, 그 수를 마지막으로 하여 만들 수 있는 증가수열의 길이는 왼쪽에 위치한 그보다 작은 값을 마지막으로 하여 만들 수 있는 증가수열의 길이보다 길다. 라는 것이다.

 

따라서 풀이는 간단하다.

1. 왼쪽에서부터 오른쪽으로 진행하면서 하나씩 숫자를 고른다.
   1. 고른 숫자와 그 오른쪽에 있는 숫자들을 비교한다.
   2. 만약 오른쪽에 있는 숫자가 더 크고, "증가수열 길이 값"이 같다면, 그 숫자들의 "증가수열 길이 값"을 1 증가시킨다.
2. 모든 수열의 숫자에 대해 위 과정을 반복한다.
3. "증가수열 길이 값"중에서 가장 큰 값을 찾아서 반환한다.

위에서 "증가수열 길이 값이 같다면" 이라는 조건이 있다.

만약 오른쪽에 있는 수의 값이 더 크다고 치자. 그런데 그 수의 증가수열 값이 더 크다면? 무시하면 된다.

왜냐하면 그 상태에서 그 값을 마지막으로 했을 때의 "최대 증가수열"은 다른 수와 조합해서 만들어진다는 의미이기 때문이다. 글로 읽어서는 이해가 잘 안될수도 있는데, 조금만 곰곰히 생각해보면 이해할 수 있을 것이다.

그렇다면 오른쪽에 있는 큰 값의 증가수열 값이 더 작다면?

그런 일은 없다. 만약 그런 일이 있다면 프로그램을 잘못 짠거다.

 

코드를 보면서 이해하길 바란다.

//#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
 
int part(int N);
 
int main() {
    int N;
    scanf("%d", &N);
    printf("%d\n", part(N));
}
 
int part(int N) {
    int** ary = new int* [N];
    for (int i = 0; i < N; i++) {
        ary[i] = new int[2]{ 0, 1 };
        int value;
        scanf("%d", &value);
        ary[i][0] = value;
    }
 
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            if (ary[i][0] < ary[j][0] && ary[i][1] == ary[j][1])
                ary[j][1]++;
    int max = 0;
    for (int i = 0; i < N; i++) {
        if (max < ary[i][1])
            max = ary[i][1];
        delete[] ary[i];
    }
    delete[] ary;
    return max;
}