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

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

이분 탐색을 이용한 문제이다. lis 알고리즘을 이용하여 문제를 해결했다. 입력받은 값들을 벡터 result에 차례대로 넣어주는데 이때 현재 백터에 들어갈 값이 result.back()보다 작다면 lower_bound를 통해 같거나 큰 값이 있는 위치를 찾아 덮어씌워 주었다. 이를 반복하면 가장 긴 증가하는 부분 수열을 얻을 수 있고 이때의 벡터의 크기를 출력해주었다. 아이디어가 떠오르지 않았던 문제였다. lis 알고리즘에 대한 것과 lower_bound가 이분 탐색을 이용한다는 것도 처음 알게되었다. 이번 문제에서는 lower_bound를 연습 겸 직접 구현해서 풀어보았다. 새로 알게된 것들에 대해 잘 기억해두어야 겠다.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> v, result;

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

        if (result[mid] < key) {
            start = mid + 1;
        }
        else {
            end = mid;
        }
    }

    return end;
}

void solution() {
    result.push_back(v[0]);

    for (int i = 1; i < N; i++) {
        int now = v[i];

        if (now > result.back()) result.push_back(now);
        else {
            int idx = my_lower_bound(0, result.size() - 1, now);
            result[idx] = now;
        }
    }

    cout << result.size();
}

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

    cin >> N;

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

    solution();

    return 0;
}