백준 11722 가장 긴 감소하는 부분수열(dynamic programming)

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

11722번: 가장 긴 감소하는 부분 수열

#include <iostream>

using namespace std;

const int MAX = 1000;
int N;
int arr[MAX];
int dp[MAX];
int sum;

void maxSum()
{
    for (int i = 0; i < N; i++)
    {
        dp[i] = 1;
        for (int j = 0; j <= i; j++)
        {
            if (arr[i] < arr[j] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;
        }
    }
    for (int i = 0; i < N; i++)
    {
        if (dp[i] > sum)
            sum = dp[i];
    }
    cout << sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    maxSum();
}

 

for(int i = 0 ; i < N ; i++){

    for(int j = 0 ; j < i ; j++){



        }

}

 

이 이중 loop 모양이 전체 크기를 제한해서 잘게 쪼개서 계산하고, 전체 크기를 좀 더 크게 만든 다음 다시 잘게 쪼개서 계산하는 dynamic programming의 전형적인 모양이라는 것을 항상 염두해두고 풀어야한다.

 

이 문제에서 애를 먹은 부분은 두 부분이다.

 

 dp[j] + 1 > dp[i]

사실 감소하는 부분수열이기 때문에 앞 조건인 arr[i] < arr[j] 은 금방 파악이 된다.

하지만, 이 조건은 쉽게 파악이 되지 않았다. 왜냐하면 모든 경우에서 dp[j] + 1 > dp[i] 가 성립하지 않겠냐는 생각 때문이었다. arr 배열과 dp 배열을 그려놓고 천천히 따라가보았다. testcase인 [10, 30, 10, 20, 20, 10] 에서 i가 맨 마지막 10에 위치할 때 이 조건이 빛을 발한다.

 

i가 두번째 20에 위치하고 j가 끝까지 다 돌아갔을 때 dp는 [1, 1, 2, 2, 2, 마지막으로 구해야할 수] 가 된다. i가 마지막으로 구해야할 수에 위치하고 j가 첫번째 20에 도착했을 때 가장 긴 감소하는 부분수열은 30, 20, 10이 돼서 마지막으로 구해야할 수가 3으로 갱신되고 j는 두번째 20에 도착한다. 이때  dp[j] + 1 > dp[i] 이 조건이 존재하지 않는다면 이 20을 또 담게 된다. 하지만, dp[j] + 1 > dp[i] 이 조건이 존재함으로 인해 중복임을 파악하고 다시 담지 않는다.

 

for (int i = 0; i < N; i++)
    {
        if (dp[i] > sum)
            sum = dp[i];
    }
    cout << sum;

 

계속 출력을 dp[N-1]로 했다. testcase와 같이 배열 내의 최솟값이 배열 맨 마지막에 위치할 경우에는 문제가 되지 않는다. 하지만 최솟값이 배열 맨 마지막에 위치하지 않는 경우가 존재할 수도 있기 때문에 이러한 출력 과정을 거쳐야 한다.

 

잘은 못하지만 뭔가 조금씩 이해가 가고 있는 것 같다. 사실 이해가 가고 있다기 보다는 점점 더 익숙해져가는 것 같다. 아주 조금 재미있어졌다.  

 

다시 풀다가 알게 됐는데

dp[i] = dp[j] + 1;  이 부분을

dp[i] += 1; 로 표현하는 것이 훨씬 더 직관적일 것 같다.(내가 이해하기 편하다.)