[Gold 2] 12015 가장 긴 증가하는 부분 수열

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

 

이 문제는 이진 탐색 알고리즘을 사용하여 해결하였다.

 

이진 탐색을 사용해야하는 이유는 N의 최대가 1000000이므로

DP를 사용 시 2중 반복을 사용해야하기 때문에 10^12가 되므로 1초를 초과하게 된다.

 

따라서 이진 탐색을 사용해 부분 수열의 길이를 구해야한다.

 

초기 A[0]를 result 배열에 삽입한다.

이후 1부터 N까지 반복을 진행한다.

result 배열에 최근에 넣은 값과 A[i]와의 값 비교를 통해

A[i]가 더 큰 경우 부분 수열의 후보군에 해당하므로 result 배열에 삽입한다.

하지만 A[i]가 작거나 같은 경우 이진 탐색을 통해 A[i]가 들어갈 위치를 찾게된다. 

 

아래는 알고리즘을 구할 때 도움이 된 블로그 글이다.

https://velog.io/@junttang/BOJ-12015-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5-C

BOJ - 12015 가장 긴 증가하는 부분 수열 2 해결 전략 (C++)

 

 

#include <iostream>
#include <vector>
using namespace std;

int N;
int A[1000000];
int answer;
vector<int> result;

int binary(int key){
    int st = 0, en = result.size() - 1;
    while(st < en){
        int mid = (st + en) / 2;
        if(key > result[mid])
            st = mid + 1;
        else
            en = mid;
    }
    return en;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>N;
    for(int i = 0;i<N;i++)
        cin>>A[i];
    
    result.push_back(A[0]);
    answer = 1;
    for(int i = 1;i<N;i++){
        if(result.back() < A[i]){
            result.push_back(A[i]);
            answer++;
        }
        else{
            int idx = binary(A[i]);
            result[idx] = A[i];
        }
    }
    cout<<answer;
    
}