[알고리즘 문제] 백준11053 - 가장 긴 증가하는 부분 수열

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

11053번: 가장 긴 증가하는 부분 수열

최장 증가 수열(Longest Increasing Subsequence), LIS라고 불리는 문제 입니다.

 

[10, 20, 10, 30, 20, 50]가 있을 때 증가하는 부분 수열을 구해보면 다음과 같습니다

 

[10,20]

[10,20,30]

[10,20,30,50]

 

[20,30]

[20,30,50]

 

[10,30]

[10,30,50]

 

[30,50]

 

[20,30]

 

여기서 [10,20,30,50]가 수열의 길이가 제일 길기 때문에 정답이 됩니다.

 

문제를 해결하기 전에 [4,6,2,7,9,1,2] 에서 최대값을 구하는 방법을 생각해 보겠습니다. LIS구하는 문제와 정확히 같지는 않지만(LIS는 2중 for문을 사용) 어쨋든 비슷한 논리로 동작합니다. 먼저 int max=0을 선언해놓고, for문을 돌면서 if (arr[i] > max) -> max = arr[i] 과정을 수행해 줍니다. 즉, 배열을 순회하면서 각각의 인덱스를 비교하여 어떤 기준값보다 큰 값이 있음연 기준값을 수정해주는 과정입니다. 

 

이 문제도 최대값 구하는것과 같이 비슷한 논리이며, dp를 사용하여 해결할 수 있는데, 먼저 각각의 숫자의 LIS를 저장하는 dp[]를 선업합니다. 예를 들어서 arr[3]에 20이라는 값이 들어있을 때 dp[3]에는 20의 LIS값이 들어가 있습니다.

 

[10, 20, 10, 30, 20, 50]에서 "30"의 LIS를 구한다고 가정해 봅시다. 현재 dp의 [1,2,0,0,0,0] 입니다. 30이전의 최대 LIS값을 찾기 위해서 30 앞에 있는 값과 모두 비교를 해줍니다.

 

1. arr[4]와 arr[1] 

30 > 10이기 때문에 30이 10오른쪽에 있습니다. 이는 dp[1](10의 LIS 값)에 +1을 의미합니다. 일단은요. 아직 2~4에서 LIS가 더 큰값이 존재할 수도 있습니다. 아직 모르기 때문에 "일단은" cnt에 cnt와 dp[1]중 더 큰 값을 저장해 놓습니다.

 

2. arr[4]와 arr[2]

30 > 20이기 때문에 30이 20오른쪽에 있습니다. 이는 dp[2]에 +1을 의미합니다. 마찬가지로 3 ~ 4에서 LIS가 더 큰 값이 있을 수 있기 때문에 cnt에 cnt와 dp[1] 중 더 큰 값을 저장해 놓습니다.

 

3. arr[4]와 와arr[3]

30 > 10 입니다. 1번 과정을 반복해야 하는데, 현재 cnt 값에는 2가 들어가 있습니다. arr[3]은 아직 0이기 때문에 cnt는 그대로 2입니다.

 

--> 지금까지 30 이전의 최대 LIS 값을 찾는 과정을 하였으며 그 값은 cnt에 저장된 2 입니다. 이는 [10, 20, 10, 30, 20, 50] 부분의 최대 LIS 값이며 여기서 30이 추가되기 때문에 cnt+1값을 dp[4]에 넣어 줍니다. 

 

다시 한번 설명하면, 구하려는 n숫자 이전의 최대 LIS 값을 구합니다. 어떤 값이 LIS 인지 모르기 때문에 n 숫자 앞까지 반복문을 돌면서 최대 LIS을 구합니다. 이는 배열에서 최대값을 구하는 방법과 같습니다. 그리고 반복문이 끝났을 때, n 숫자 이전의 최대 LIS가 구해지겠죠. 이때 LIS 값은 n을 포함하지 않은 값이기 때문에 n숫자의 LIS는 +1을 해줍니다.

 

그리고 코드에서 dp[i]=1을 해준 이유는, 하나만 있는 숫자로 1길이를 가지기 떄문입니다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1001] = {0};
int dp[1001] = {0};

int main()
{
    int n;
    int result = 0;

    cin >> n;

    int arr[1001] = {0};
    int dp[1001] = {0};

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

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

    cout << result;
    return 0;
}