백준 12015번, 가장 긴 증가하는 부분 수열 2(C, C++)

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

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

※틀린 풀이

#include<iostream>

using namespace std;
int cache[1000001];
int A[1000000];
int N;

int Lis(int start){
    int &ret = cache[start+1];

    if(ret != -1){
        return ret;
    }
    ret = 1;

    for(int next = start + 1; next < N; ++next){
        if(start == -1 || A[start] < A[next]){
            ret = max(ret, Lis(next) + 1);
        }
    }
    return ret;
}

int main(){

     cin >> N;
     for(int i = 0; i < N; i++){
         cin>>A[i];
         cache[i] = -1;
     }
     cache[N] = -1;
     cout<<Lis(-1)-1;
     return 0;
}

위의 코드는 동적계획법(DP)을 이용한 풀이입니다.

함수의 결과를 저장하는 장소를 마련하고, 한 번 계산한 값을 저장했다가 재활용하는 방식,

메모이제이션을 사용했습니다.

 

하지만 위 코드 방식대로 실행시키면

O(n)개의 부분 문제를 갖고 하나를 해결할 때마다 O(n)시간의 반복문을 순회하고

따라서 O(n^2)의 시간 복잡도를 갖습니다.

 

주어진 N이 100만까지 정해져있어 결국엔 시간초과를 발생할 수 밖에 없어 다른 방식으로 풀어야합니다.

 

※올바른 풀이

#include<iostream>

using namespace std;

int N;
int A[1000001];
int ret;
int Lis[10000001];

// 해당 문제는 dp로 풀수 없다. 왜냐하면 n의 값이 100만까지 주어져 있어 시간초과가 날 수 있기 때문이다.

int binary_search(int start, int end, int num){
    int ret;
    while(start <= end){
        int mid = (start + end) / 2;
        if(Lis[mid] >= num){
            ret = mid;
            end = mid -1;
        }else{
            start = mid + 1;
        }
    }
    return ret;
}

int main(){
    cin >> N;
    int length = 1;
    for(int i = 0; i < N; i++){
        cin>>A[i];
    }
    Lis[0] = A[0];

    for(int i = 1; i < N; i++){
        if(Lis[length - 1] < A[i]){
            Lis[length] = A[i];
            length++;
        }else{
            int idx = binary_search(0, length-1, A[i]);
            Lis[idx] = A[i];
        }
    }
    cout<<length;
    return 0;
}

LIS배열 구성하고, 조건에 부합하는 A배열의 원소들을 만들어진 배열에 넣는 방식으로 풀어보겠습니다.

 

1) A배열의 제일 첫 번째 원소는 LIS에 넣습니다.

 

2) LIS 배열의 가장 큰 값과 다음 번째의 A배열 원소와 비교합니다. 3-1, 3-2 둘 중 하나를 진행.

 

3-1) LIS 배열의 가장 큰 값이 A배열의 원소보다 작을 경우, LIS배열에 가장 오른쪽에 위치하게 됩니다. 

 

3-2) LIS의 가장 큰 값이 크기가 클 경우, 이분 탐색에 의해 적절히 배치 되어 A배열의 원소로 바뀌게 됩니다

 

4) 다시 2번으로 돌아가 반복합니다.

 

예시로 A의 원소 {10, 20, 50, 40, 45, 46, 30, 70}이 있습니다.

가장 긴 증가하는 부분 수열은 {10, 20, 40, 45, 46, 70}입니다.

 

위 코드의 방식대로 적용해본다면,

{10}

{10, 20}

{10, 20, 50}

{10, 20, 40}

{10, 20, 40, 45}

{10, 20, 40, 45, 46}

{10, 20, 30, 45, 46}

{10, 20, 30, 45, 46, 70} -> 길이가 6인 가장 긴 증가하는 부분수열이 나오게되지만

직관적으로 구할 수 있는  {10, 20, 40, 45, 46, 70}와는 다릅니다.

LIS배열의 원소들은 다를지라도, 길이는 같다라는 것을 알 수 있습니다.

이 문제의 아이디어는 '오름차순을 유지할 수 있도록' 적절하게 이분탐색을 이용해야합니다.