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

24 Oct 2023 in Study on Coding Test

이분탐색을 활용해볼 수 있는 문제

정답제출코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> ans;

int IdxBinSearch(int a)
{
    int L = 0, R = ans.size()-1, M;

    while (L < R)
    {
        M = (L + R) / 2;

        if (ans[M] >= a)
            R = M;
        else
            L = M + 1;
    }

    return R;
}

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

    int N, Idx;
    cin >> N;

    vector<int> vec;
    vec.resize(N);

    for (int i = 0; i < N; ++i)
        cin >> vec[i];
    
    ans.push_back(vec[0]);

    for (int i = 1; i < N; ++i) {
		if (vec[i] > ans.back())
			ans.push_back(vec[i]);
		else {
			Idx = IdxBinSearch(vec[i]);
			ans[Idx] = vec[i];
		}
	}

	cout << ans.size();
}

사실 이분 탐색을 활용해서 풀어볼 수 있는데

다만 아이디어를 도출하는 것이 어려웠던 것 같다.

다행히도, 이 문제는 LIS의 길이를 정답으로 요구하고 있기 때문에

LIS가 바뀌어야 한다고 해도 길이는 그대로 보존이 된다.

예를 들어, LIS가 지금까지

10 15 20

이었다고 하자.

그런데 새로운 LIS를 찾아버려서

10 15 19 20

이 된다고 해도 길이는 3이상이기 때문에 LIS를 엎을 필요는 없다.

그래서

ans.push_back(vec[0]);

이라는 코드로 맨 처음 원소를 먼저 정답 벡터에 넣어주는 것이다.

그리고 부담없이 ans 벡터 내에서 이분탐색을 진행하면서 어디에다가 넣어주어 정답 길이를 늘려줄 지 생각하면 된다.