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

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

📝문제링크 : www.acmicpc.net/problem/11053

 

지금까지 풀었던 DP 중 제일 어려웠다. 정답코드를 보고도 접근 방법이 잘 연상되지 않았다.
solved.ac 등급이 silver2 던데, silver1 문제보다 어려운 거 같은데...🤔
가장 긴 증가하는 부분 수열은 LIS 라고도 불리는데, 유명한 개념이니까 확실히 알고 넘어가는게 좋을 것 같다.

 

접근 과정

1. DP니까 당연하게도(?) memoization으로 접근해봐야지.

• $dp[i]$ : arr[i]이 배열의 마지막 원소일 때, 가능한 가장 긴 증가하는 부분 수열의 길이가 저장된다.
• dp[i] 에 저장될 값은, arr[i - 1] 까지의 가장 긴 증가하는 부분 수열에 arr[i] 값을 붙일지 말지 결정한 후 결정되겠지?

 

2. 증가하는 부분 수열이 어떤 성질을 갖고 있는지 파악해서, arr[i] 이전의 가장 긴 증가하는 부분 수열을 찾아보자.

• 마지막 원소가 arr[i]라면, 가장 긴 증가하는 부분 수열은 아래와 같은 성질을 갖는다.
  • arr[i] 보다 앞에 있고 $( j < i )$
  • arr[i] 보다 작은 수로 끝난다. $( arr[j] < arr[i] )$

 

3. 구현

i 는 배열의 처음부터 끝까지, j 는 0부터 i 보다 작을 동안 도는 이중 for문이 필요하겠네.

그리고 두 번째 성질을 if문으로 추가한 후 dp[i] 값 계산.

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);
    }
}

max() 함수에서,

dp[i] 가 선택되는 경우는, 현재 arr[j] 값을 취하고 넘어가는게 더 이득인 경우이고,

dp[j] + 1 가 선택되는 경우는, 현재 arr[j] 값을 취하고 넘어가는게 더 이득인 경우이다.

 

전체 소스코드

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1001];
int arr[1001];

int main() {
    
    int n;
    int ans;

    ans = 0;
    //get input
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    //solve
    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);
        ans = max(ans, dp[i]);
    }

    //print answer
    cout << ans << '\n';
    return 0;
}

 

• 시간복잡도 : $O(n^2)$

 

trivia

• 이 문제는 어려워서 유튜브에도 검색해보다가, 다른 알고리즘을 이용해 푸는 방법도 있다는 걸 알았다. 입력값의 범위가 큰 경우엔 꼭 그 알고리즘으로 풀어야한다던데, 다른 알고리즘 공부할 때 이 문제를 꼭 다시 찾아봐야겠다.
• plzrun 님이 추천한 알고리즘 공부 순서대로 공부하고 있는데 이제 DP 한 세트가 끝났다. 
• 그러고보니 그동안 시간복잡도는 하나도 고려하지 않고 있었네 ;;;
• 이제부터 해야지.