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

가장 긴 증가하는 부분 수열 (백준 11053번)

개념 : LIS, LCS

난이도 :

링크 : LIS : https://www.acmicpc.net/problem/11053

---

$LIS$(Longest Increasing Subsequence)는 가장 긴 증가하는 부분수열로 $LCS$와 함께 교과서에 가장 많이 등장하는 $DP$문제이다.

이 문제는 그 특성만으로 해결하는 방법이 있고, $LCS$의 일반화 문제로 생각하여 해결하는 방법이 있다. $LCS$를 잘 모른다면 LCS 개념을 공부하고 오자.

조금만 생각해보면 어떠한 배열의 $A$의 $LIS$는 다음과 같음을 알 수 있다.

$ B = $ 중복 원소를 제거하고 정렬된 $A$

$ M = size(B) $

$LIS(A[1 \dots N]) = LCS(A[1 \dots N], B[1 \dots M]) $

$LIS$에는 중복되는 원소는 존재할 수 없으니, $A$ 중복을 제거하고, 모든 원소들이 증가하는 상태로 만든 배열과의 $LCS$가 곧 $LIS$가 됨을 알 수 있다.

코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int dp[1010][1010];
int arr[1010];
int arr2[1010];
int n, m;

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

    memcpy(arr2, arr, sizeof(int) * n);
    sort(arr2, arr2 + n);
    m = unique(arr2, arr2 + n) - arr2;


    for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j) {
        if (arr[i-1] == arr2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
        else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }

    cout << dp[n][m];
}

그리고 $LCS \ 9$을 공부하면서 다음과 같은 사실을 알게되었다.

• 배열 $A$의 $LIS$는 $(A[i], -i)$로 좌표 압축하여 만든 배열 $B$와 배열 $[1 \dots N]$ 과 같다

같은 수를 만나더라도, 앞에 같은 수가 있으면 $LCS$에 포함시키면 안되기 때문에 $-i$로 정렬해야하는 것이다.

아래의 예시를 보면 이해가 될 것이다.

배열 : $ [20, 20] $

좌표압축배열 : $ [(20, -1), (20, -2)]$

좌표압축 : $[2, 1]$

같은 20의 값이더라도 앞에 같은 수가 있으면 안되기 때문에 가장 뒤에 있는 수가 가장 작은 수를 갖게 되어야 하는 것이다.

아래는 코드이다.

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int dp[1010][1010];
int arr[1010];

pii compress[1010];
int n;

int main() {
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> arr[i];
        compress[i] = {arr[i], -i};
    }
    sort(compress, compress + n);
    for (int i=0; i<n; ++i) {
        arr[i] = (int)(lower_bound(compress, compress + n, pii{arr[i], -i}) - compress) + 1;
    }    

    for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) {
        if (i == arr[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
        else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }

    cout << dp[n][n];
}

두 풀이 모두 중간 전처리에 $O(NlogN)$의 시간이 소요되나 $O(N^2)$의 풀이를 갖는다.