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

문제

접근 방법

가장 긴 증가하는 부분 수열을 이분 탐색을 통해 관리하는 문제이다.
새로운 값이 들어왔을 때 현재 값보다 크거나 같은 값이 없다면 추가해 주고 존재한다면 교체해 준다.

가장 큰 값이 들어오면 배열의 길이가 길어지고 크거나 같은 값을 현재의 값으로 바꾼다면 같은 값이었다면 그대로고 큰 값이면 작아지기에 재구축된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N;
    vector<int> dp;
    cin >> N;
    for (int i = 0, j; i < N; ++i)
    {
        cin >> j;
        auto it = lower_bound(dp.begin(), dp.end(), j);
        if (it == dp.end())
            dp.push_back(j);
        else
            dp[it - dp.begin()] = j;
    }
    cout << dp.size();
    return 0;
}

풀이

어떻게 풀어야 하는지 알고 이해하면 쉬운데 그걸 깨닫기 어려운 문제 같다.