[백준 12015] 가장 긴 증가하는 부분 수열 2

가장 효율적인 이진탐색으로 자리 찾아서 넣어주거나 v.push_back해서 푸는 LIS

N < 1,000,000 이기 때문에 dp로 풀면 시간초과 남

 

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;

vector<int> lis;

int binary_search(int x)
{
    int left = 0;
    int right = lis.size() - 1;
    int mid;

    while (left <= right)
    {
        mid = (left + right) / 2;

        // 값과 똑같으면 바로 반환
        if (x == lis[mid])
        {
            return mid;
        }

        // 아니면 조여나가기
        if (x < lis[mid])
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }

    return left;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    int x;
    for (int i = 0; i < N; i++)
    {
        cin >> x;

        int pos = binary_search(x);

        // 모든 수보다 크면 lis에 push_back
        if (pos == lis.size())
        {
            lis.push_back(x);
        }
        else
        {
            lis[pos] = x;
        }
    }

    cout << lis.size();

    return 0;
}