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

11 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/12015

나의 풀이

처음 이 문제를 접근할 때는 이전에 풀었던 11722 가장 긴 감소하는 부분 수열과 동일하게 DP로 해결하려 했다. 하지만 이 문제는 N이 최대 1000000으로 증가하였기 때문에 DP로 문제를 풀면 O(N^2)의 시간 복잡도로 시간 초과가 발생하게 되어 이진 탐색을 이용한 방법으로 문제를 해결하였다.
먼저 벡터 B는 다음과 같이 정의한다.
B[i-1] = 길이가 i인 증가 수열의 마지막 값 중 최솟값 (i>=1)
벡터 B를 위와 같이 정의하는 이유는 B의 최종적인 길이가 가장 긴 증가하는 부분 수열의 길이와 같고, 증가하는 부분 수열이 최대로 길어지기 위해서는 마지막 값이 최대한 작아져야하기 때문이다.

B벡터에 새로운 값 x를 추가하는 과정은 다음과 같다.

• B벡터의 마지막 값보다 x가 크다면(B.back() < x) 기존 증가 수열뒤에 추가할 수 있기 때문에 B의 마지막 값으로 x를 추가한다.
• 만약 B벡터의 마지막 값보다 x가 작다면 길이가 j인 증가 수열의 마지막 최솟값을 x로하는 j를 이진 탐색을 통해 찾고, B[j] = x로 바꿔준다.

예를 들어 A = {8, 3, 6, 1, 4} 일 때 A[0] = 8로 초기 B = {8}이 된다. 이후 A[i] 값을 벡터 B에 추가한다.
x = A[1] = 3, B.back() = 8 —> 8 > 3 —> B = {3}
x = A[2] = 6, B.back() = 3 —> 3 < 6 —> B = {3, 6}
x = A[3] = 1, B.back() = 6 —> 6 > 1 —> B = {1, 6}
x = A[4] = 4, B.back() = 6 —> 6 > 4 —> B = {1, 4}
최종 B = {1, 4} —> 최종 B의 길이는 = 가장 긴 증가하는 부분 수열의 길이 = 2
이 과정으로 정답을 구하면 O(NlogN)으로 시간초과를 피해 문제를 해결할 수 있다.

풀이 코드 : 12015 가장 긴 증가하는 부분 수열2

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, num;
    vector<int> A;
    vector<int> B;
    cin>>N;

    for(int i=0;i<N;i++){
        cin>>num;
        A.push_back(num);
    }

    B.push_back(A[0]);
    for(int i=1;i<N;i++){
        if(B.back() < A[i]){
            B.push_back(A[i]);
        }
        else if(B.back() > A[i]){
            int start = 0;
            int end = B.size();
            int mid;
            while(start<end){
                mid = (start+end)/2;
                
                if(B[mid] < A[i]){
                    start = mid + 1;
                }
                else{
                    end = mid;
                }
            }
            B[end] = A[i];
        }
    }
    cout<<B.size();

}

채점결과