백준 12738 - 가장 긴 증가하는 부분 수열 3

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 것이다.

유명한 DP문제인 LIS를 구현하면 된다.

 

하지만, 해당 문제의 난도가 높게 평가된 이유는 아마 시간 초과를 해결해야 하기 때문이다.

보통의 LIS는 $O(N^2)$의 시간복잡도를 갖는다.

i번째 이전의 수중 i번째 수보다 더 작은 수가 갖고 있는 가장 긴 증가하는 부분 수열에 마지막에 i번째 수를 추가하면 되기 때문이다.

따라서, N개의 수에 대해 N번의 탐색을 통해 자신보다 작은 수들을 탐색하는 과정을 진행하기 때문에  $O(N^2)$이다.

 

하지만, 이를 개선하면  $O(NlogN)$만에 문제를 풀 수 있다.

그 방법은 이진 탐색을 활용하는 것이다.

이진 탐색을 활용하면 자신보다 앞에 있는 수 중 자신보다 작은 수에 대해 탐색하는 과정을 줄일 수 있기 때문이다.

하지만, 조금 의아한 부분이 존재할 것이다.

자신보다 작은 수를 찾는다고 하더라도 꼭 그 수가 가장 긴 증가하는 부분 수열 중 가장 긴 수를 가지는 게 보장되지 않기 때문이다.

여기서 약간의 트릭이 필요하다.

각 길이의 수에 대해 마지막에 나온 수를 알고 있다고 생각해보자.

예를 들어.

6
10 20 10 30 20 50

일 때, 30에 대해 연산을 진행 중이라 하면 LIS는 {10, 20, 30}이 될 것이다.

왜냐하면, 30을 더하기 이전에 LIS는 {10, 20}이었기 때문이다.

이때 30은 자신이 들어갈 위치를 이진 탐색을 통해 찾을 수 있다.

{10, 20}에서는 자신보다 작거나 같은 수가 없기 때문에 마지막에 삽입이 되어야 한다.

만약, 이전 LIS가 {10, 20, 40}이었다면 40이 있는 위치에 30이 들어가는 게 맞다.

즉, {10, 20, 30}으로 LIS가 바뀌게 된다는 것이다.

이를 갱신하는 이유는 30보다 크거나 같은 가장 빨리 나오는 숫자를 30으로 갱신하는 것이 LIS를 구성하는데 유리하기 때문이다.

 

만약, LIS가 {10, 20, 30}인 상황에서 50을 추가한다고 생각해 보자.

50보다 크거나 같은 수는 없다.

따라서, 30 뒤에 50을 추가하여 {10, 20, 30, 50}이 LIS가 된다.

 

이러한 로직이 올바르게 동작하는 이유는 LIS는 자신보다 작은 수들이 몇 개나 순서대로 존재하는지를 세면 되기 때문이다.

정리하자면, 이러한 로직에 최적화된 lower_bound를 사용하여 현재까지 구성한 LIS에서 자신이 들어갈 위치를 찾은 뒤 자신의 위치가 가장 뒤라면 LIS의 길이를 증가시키면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> N;

    vector<int> nums(N);
    vector<int> LIS(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> nums[i];
    }

    int len = 0;
    for (int i = 0; i < N; i++)
    {
        int pos = lower_bound(LIS.begin(), LIS.begin() + len, nums[i]) - LIS.begin();
        LIS[pos] = nums[i];
        
        if (pos + 1 > len) len++;
    }

    cout << len;

    return 0;
}

---