문제

풀이

기존에 DP로 풀었던 문제와 같은 문제이다. 그러나, 같은 알고리즘으로 하면 testcase의 arr.size()가 커져서 시간초과가 나는 문제이다. 문제의 알고리즘은 다음과 같다.

주어진 testcase의 첫번째 값을 result vector에 넣는다.
iteration으로 N번째까지 조건에 부합하는지 안하는지 확인한다.
2-1. testcase 수열의 i번째 값이 result 벡터의 맨 마지막 값보다 크면 result vector에 그 값을 push_back한다.
2-2. result의 맨 마지막 값보다 작으면 그 수보다 큰 값이 가장 먼저 나오는 index에 그 값으로 대체한다. (이분 탐색 사용)
result.size()로 정답 출력한다.

이는, 새로운 값이 나왔을 때, 푸쉬를 하되 이어 붙일 수 없는 경우에 그 값이 기존의 증가하는 부분 수열을 좀 더 작은 값들로 대체하는 것이다. 이는 원래보다 작은 값으로 대체함으로써 새로운 값이 나왔을 때 그 값이 추가될 수 있도록 해주는 것이다. 이를 통해 최대 길이를 확보할 수 있는 것이다. +) 하지만, 이 알고리즘은 최대 길이라는 숫자의 값만 보장한다. result 배열의 값이 최대 부분 수열이라는 것은 보장하지 않는다. 문제에서는 최대 길이만을 요구하였고, 중간 중간 result의 마지막 값보다 작은 값이 나올 때 idx를 찾아 단지 1:1 교체하는 것은 결과적으로 최대 길이에 영향을 주지 않는다. 최대 부분 수열은 추적하는 문제는 14003번에서 진행된다.

소스 코드

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

int binarysearch(vector<int> &a, int num){
    int ans = 0;
    int left = 0;
    int right = a.size()-1;
    
    while(left<=right){
        int mid = (left+right)/2;
        
        if(a[mid] >= num){
            ans = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }

    return ans;
}

int main(){
    int N;
    scanf("%d", &N);
    
    vector<int> arr(N);
    for(int i = 0 ; i<N; i++){
        scanf("%d", &arr[i]);
    }
    
    vector<int> result;
    result.push_back(arr[0]);
    
    for(int i = 1; i<N; i++){
        if(result.back() < arr[i]) result.push_back(arr[i]);
        else{
            int idx = binarysearch(result, arr[i]);
            result[idx] = arr[i];
        }
    }
    
    printf("%d\n", result.size());
}

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

"이분탐색"

문제

풀이

소스 코드

CATALOG

FEATURED TAGS