[백준(BOJ)] 가장 긴 증가하는 부분 수열 2(12015번)_C++

문제를 어떻게 풀어야할지 모르겠다면 LIS에 대해 공부를 좀 해보도록 하자!

 

대강 그런가보다 하면서 넘어가지 말고 정확하게 코드 한줄 한줄을 분석하면서

그 의미, 이유를 고민하면 도움이 많이 되는 좋은 문제다.

 

LIS에 대해 따로 설명하진 않겠다.

설명을 잘 해놓은 블로그나 유튜브 영상이 정말 많다.

공부를 한 번 하고, 정답 코드를 분석하면 어느 정도 이해가 될 것인데 update_idx가 잘 이해되지 않을 수가 있다.

이 부분에 대해서만 간단하게 설명하도록 하겠다.

 

binary_search에서는 seq배열 즉, LIS에서 a[cur]보다 크거나 같은 첫번째 원소를 이분 탐색으로 찾는다.

단. seq에 a[cur]과 같은 원소가 없을수도 있으므로 정확한 위치를 구하기 위해서는 추가적인 조치를 해야한다.

내 코드에서는 update_idx가 그 정확한 위치다.

a[cur]이 들어갈 상황은 seq[mid]가 a[cur]보다 크거나 같을 때이다. 당연하다. a[cur]보다 크거나 같은 원소가 있는 위치에만 a[cur]은 들어갈 수 있다. 즉, 이 상황에서 update_idx를 계속 mid로 갱신하면 a[cur]과 가장 가까운 값의 위치를 구할 수 있다.

 

잘 이해되지 않는다면 직접 예시를 들어서 이해해보도록 하자.

 

---

정답

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> a, seq;

void binary_search(int cur){
    int start = 0;
    int end = seq.size() - 1;
    int update_idx = 2e9;

    while (start <= end){
        int mid = (start + end) / 2;

        if (seq[mid] >= a[cur]){
            update_idx = mid;
            end = mid - 1;
        }
        else
            start = mid + 1;
    }

    seq[update_idx] = a[cur];
}

void LIS(){
    seq.push_back(a[0]);

    for(int i = 1; i < n; i++){
        if (a[i] > seq.back())
            seq.push_back(a[i]);
        else
            binary_search(i);
    }
}

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

    //input
    cin >> n;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        a.push_back(temp);
    }

    //find LIS
    LIS();

    //output
    cout << seq.size();
}