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

백준의 가장 긴 증가하는 부분 수열(11053) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

간단한 예를 하나 통해서 문제에 접근해보자.

다음과 같은 배열이 있을 때, 가장 긴 증가하는 부분 수열의 값을 찾아보자.

[ 1 , 2 , 1 , 3 , 4 , 2 ]

먼저 첫 번째 값인 '1' 부터 알아보자.

첫 번째 값 까지 왔을 때, 가장 긴 증가하는 부분 수열의 길이는 얼마일까 ?? 바로 '1'이다. 왜냐하면, 첫 번째 값인 '1' 자체 만으로도 길이가 1인 수열이 성립하게 되고, "그 전에" 어떠한 숫자도 나오지 않았기 때문에 '1'이상의 값이 나올 수가 없다.

따라서 첫 번째 값인 '1'까지 왔을 때, 가장 긴 증가하는 부분 수열의 길이는 '1'이다.

두 번째 값인 '2'로 가보자.

두 번째 값 까지 왔을 때, 가장 긴 증가하는 부분 수열의 길이는 ?? 바로 '2'이다. 왜냐하면, 첫 번째 값인 '1'이 두 번째 값인 '2'보다 작기 때문에 첫 번째 값부터 수열을 이루게 되면 { 1, 2 } 라는 증가하는 수열을 성립할 수 있게 된다.

조금 다르게 표현해보면, "이전에 나온 숫자들 중에서 , 현재 값인 '2'보다 작은 값 중에서, 가장 길이가 긴 수열을 가진 '1'과 합쳐지게 됨으로써 길이가 '2'인 증가하는 부분수열을 성립" 할 수 있게 된다.

세 번째 값인 '1'로 가보자.

이 경우에는 부분 수열의 길이가 1이다. 왜냐하면 ! "이전에 나온 숫자들 중에서, 현재 값인 '1'보다 작은 값이 없기 때문" 이다.

네 번째 값인 '3'으로 가보자.

네 번째 값 까지 왔을 때, 발생할 수 있는 모든 증가하는 부분 수열을 적어보면 다음과 같은 Case들이 존재한다.

1. 첫 번째 값 - 두 번째 값 - 네 번째 값 (1 - 2 - 3)

2. 두 번째 값 - 네 번째 값 (2 - 3)

3. 세 번째 값 - 네 번째 값 (1 - 3)

네 번째 값 까지 왔을 때, 발생할 수 있는 모든 증가하는 부분 수열들이다. 당연히 이 중에서 가장 긴 증가하는 부분수열은 1번 Case인 길이가 '3'인 수열이 된다.

여기서 위에서 발생한 3가지 경우들과, 그 경우들 중에서 가장 긴 증가하는 부분 수열을 구하는 과정을 정리해서 적어보면 이렇게 표현할 수 있다.

"이전에 나온 숫자들 중에서 , 현재 값인 '3'보다 작은 값 중에서, 가지고 있는 부분 수열의 길이 중 가장 긴 부분 수열의 길이에 + 1을 한 값이 현재 값에서 발생할 수 있는 가장 긴 증가하는 부분 수열의 길이가 된다."

위의 말을 다시한번 확인해보자.

1번 Case의 경우는 1 - 2 - 3 의 순으로 뽑는 것이였는데, 이 중에서 사실 1 - 2 는, 두 번째 값인 '2'에서 발생할 수 있는 가장 긴 부분 수열을 의미한다. 즉 ! 네 번째 값인 '3'과 비교했을 때, 더 작은 값인 '2'를 가지고 있는 두 번째 값이 가지고 있는 부분 수열의 길이에 + 1을 한 길이가 1번 Case의 길이가 되는 것이다. 따라서 2 + 1 = 3 이라는 길이를 구할 수 있게 된다.

2번 Case의 경우는 위에 적어놓기는 했지만, 사실 의미가 없는 Case이다. 왜냐하면, 2번 Case는 첫 번째 값을 버리고, 두 번째 값을 선택하고 이 후, 네 번째 값을 선택하는 Case인데 , 이 과정에서 의미가 없는 행위가 들어가기 때문이다.

두 번째 값을 선택하면, 자연스럽게 첫 번째 값을 선택할 수 있게 된다. 왜냐하면, 첫 번째 값인 '1'이 두 번째 값인 '2'보다 더 작고, 이 2개를 합쳐서 만들면 길이가 2인 부분 수열을 구할 수 있는데, 굳이 첫 번째 값을 버리고 두 번째 값만을 선택한 상황에서 길이가 최대한 부분 수열이 발생하기를 기대한다 ? 너무나도 당연한 이야기겠지만, 1번 Case보다 무조건 작을 수 밖에 없는 Case이다. 그래서 사실 의미가 없는 Case이다.

3번 Case는 세 번째 값을 선택하고 네 번째 값을 선택하는 경우인데, 이 경우는 올바른 경우이지만, 최댓값이 되지 않는다.

그럼 다섯번째 값 부터는 위에서 했던 이야기를 토대로 한번 구해보자.

우리는 지금부터, "이전에 나온 숫자들 중에서, 현재 값 보다 작은 값 중에서, 가지고 있는 부분 수열의 길이 중 가장 긴 부분 수열을 가진 길이에 + 1을 한 값을 가장 긴 증가하는 부분 수열의 길이로 선택" 할 것이다.

현재 값은 '4'이다. 이전에 나온 숫자들로는 [ 1 , 2 , 1 , 3 ] 이 있다.

이 중에서 더 작은 숫자는 위에서 말한 4개의 숫자 모두 해당된다.

각 숫자들이 가지고 있는 "가장 긴 증가하는 부분 수열" 의 길이를 적어보면 , [ 1, 2, 1, 3 ] 이 된다.

이 중에서 가장 큰 값은 '3'이고 , 다섯번째 값 까지 왔을 때 발생할 수 있는 가장 긴 부분 수열의 길이는 '4'이다.

실제로 보면 , { 1 , 2 , 3 , 4 } 로 수열을 만들 경우, 길이가 4로 최대 길이의 가장 긴 부분 수열을 구할 수 있다.

마지막 값을 확인해보자.

마지막 값은 '2'이고, 이전에 나온 숫자들을 적어보면 [ 1, 2, 1, 3, 4 ] 가 있다.

이 중에서, '2'보다 더 작은 값은 [ 1, 1 ] 이 있고, 이 2개의 숫자들이 가지는 가장 긴 증가하는 부분 수열의 길이를 적어보면

[ 1, 1 ] 을 가지고 있다. 이 중 최댓값은 '1'이고 여기서 1을 더한 '2'가 마지막 값이 가질 수 있는 가장 긴 증가하는 부분 수열의 길이이다.

그럼 위의 내용을 일반화된 내용으로 한번 적어보자.

"x번째 값이 가지는 가장 긴 증가하는 부분수열의 길이를 구하고 싶다면 , 1 ~ x - 1번째 값들 중, x번째 값 보다 더 작은 숫자들이 갖는 부분수열의 길이 중, 가장 길이가 긴 부분수열의 길이에 + 1을 한 값이, x번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이이다."

이를 코드로 표현하기 위해서 본인은 1차원 배열 하나를 이용해서 표현해 주었다.

DP[] 라는 배열인데 , DP[a] = b 의 의미는 "a번째 값이 가지는 가장 긴 증가하는 부분수열의 길이는 b입니다." 이다.

그리고 2중 for문을 통해서 위에서 말한 내용을 구현해 주었다.

먼저, 1 ~ N번째 값 까지 반복하기 위한 큰 for문이 하나 필요하고 , 그 안에 for문에서는 1 ~ N - 1번째 값 까지 탐색하는 과정을 나타내주었다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    int Answer = 0;
    for (int i = 1; i <= N; i++)
    {
        DP[i] = 1;
        for (int j = i - 1; j >= 1; j--)
        {
            if (Arr[i] > Arr[j])
            {
                DP[i] = Max(DP[i], DP[j] + 1);
            }
        }
        Answer = Max(DP[i], Answer);
    }
 
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}