[C++] 백준 12015 - 가장 긴 증가하는 부분 수열 2

<문제 링크> 

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

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

<알고리즘 분류> 

 - 이분 탐색(Binary Search) 

 - 다이나믹 프로그래밍(Dynamic Programming)

<풀이> 

 - 너무나도 중요한 문제이다. 가장 긴 증가하는 부분수열을 구하는 풀이법은 크게 두 가지가 있다.

첫 번째는 길이가 N인 수열을 돌면서,

"현재의 숫자 앞에서 자신보다 작은 수이면서 가장 큰 부분수열을 가진 값 + 1"

을 구하는 시간복잡도 O(N^2)인 풀이법이 있다.

 

두 번째는 "현재의 숫자 앞에서 자신보다 작은 수이면서 가장 큰 부분수열을 가진 값" 을 수열의 길이를 index로 가지는 배열에 따로 저장해 주어, 이분탐색으로 그 위치를 구한 뒤 갱신하는, 시간복잡도 O(NlogN) 방법이 있다. 

 

이 문제의 경우 수열의 길이 N이 최대 1,000,000이므로, 첫 번째 방식을 적용하면 시간초과가 발생한다. 따라서 두 번째 방법을 쓰기로 한다. 

 

준비물은 이렇다.

  - 수열을 입력받는 vector A,

  - 해당 숫자까지 봤을 때, 가능한 가장 긴 수열의 길이를 저장하는 배열 D (=> Dynamic Programming)

  - ⭐️수열의 최대 길이를 index로 표현한 배열 num.

       (예를 들어, 수열의 최대길이가 j일때, num[j]는 j의 길이를 가진 숫자 중 가장 작은 숫자를 저장한다.)

 

준비물이 완료됐다면, 그림을 통해 이해해 보자. 주어진 수열은 [3, 5, 7, 9, 2, 1, 4, 8] 이다. 

D[i]를 돌 때마다 max값을 갱신해 주면서, 모두 순회를 마쳤다면 max값을 반환하면 된다. 

max_length는 가장 작은 수열의 길이 1(단독)을 항상 만족하기 때문에, max_length=1로 초기화하였다.

<코드> 

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std;
#define INF 1000001

int N;
vector <int> A;
int num[1000001]; // 수열의 길이를 만족하는 숫자 중 가장 작은 숫자를 저장. 
int D[1000001]; // 해당 숫자까지 보았을 때, 가능한 가장 큰 수열의 길이를 저장. 

int main(){

    cin >> N;
    for (int i=0; i<N; i++){
        int x;
        cin >> x;
        A.push_back(x);
    }
    
    for (int i=1; i<sizeof(num)/sizeof(int); i++){
        num[i] = INF;
    }

    D[0] = 1;
    num[0] = 0;
    num[1] = A[0];
    int max_length = 1;
    for (int i=1; i<N; i++){
        if (D[i] > D[i-1]){
            D[i] = D[i-1] + 1;
            num[D[i]] = min(A[i], num[D[i]]);
        }
        else {
            int index = lower_bound(num, num+sizeof(num)/sizeof(int), A[i]) - num;
            if (index == 0) index ++;
            num[index] = A[i];
            D[i] = index;

        }
        if (D[i] > max_length) max_length = D[i];
         for(int i=0; i<N; i++){
            cout << D[i] << " ";
        }
        cout << "\n"; 
    }

    cout << max_length;