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

#include <iostream>
#include <algorithm>
#include <vector>
 
int arr[1000001] = {};
std::vector<int> dp = {};
int N = 0;
 
void BinarySearch(int num)
{
    int low = 0;
    int high = dp.size() - 1;
    int mid = 0;
    int target = 1000002;
 
    while (low <= high) 
    {
        mid = (low + high) / 2;
        int now = dp[mid];
 
        if (now >= num)
        {
            if (target > mid)
                target = mid;
 
            high = mid - 1;
        }
 
        else
            low = mid + 1;
    }
 
    dp[target] = num;
}
 
void Check() 
{
    dp.push_back(arr[0]);
 
    for (int i = 1; i < N; ++i) 
    {
        if (dp.back() < arr[i]) 
        {
            dp.push_back(arr[i]);
        }
 
        else 
        {
            BinarySearch(arr[i]);
        }
    }
}
 
int main() 
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    std::cin >> N;
    for (int i = 0; i < N; ++i) 
    {
        std::cin >> arr[i];
    }
 
    Check();
 
    std::cout << dp.size();
 
    return 0;
}
 

입력을 할 때 마지막에 입력한 크기보다 크다면 바로 입력,

작다면 이전 함수 중에 이분탐색으로 본인의 수보다 큰 수를 본인과 변경합니다.

이럴 경우 내부가 순서가 달라지지만 우리가 원하는 건

숫자 순서가 아니라 순서의 갯수가 얼마나 나오는 지가 중요하기 때문이라 상관없습니다.

 

하지만 이후 더 좋은 것들을 확인했기 때문에 올려보겠습니다.

#include <bits/stdc++.h>
 
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int N;
	cin >> N;
	vector<int>table;
	table.reserve(N);
 
	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;
		auto iter = lower_bound(table.begin(), table.end(), temp);
 
		if (iter == table.end())
			table.emplace_back(temp);
		else
			*iter = temp;
	}
 
	cout << table.size();
 
	return 0;
}

이것은 입력을 할 때마다 이분탐색으로 본인보다 큰 위치를 바로 찾아냅니다.

찾을 경우 바로 그 자리에 넣어주고 계속해서 돌리면 됩니다.

너무 깔끔하고 간단해서 매우 놀랐습니다...