[BOJ]12015번: 가장 긴 증가하는 부분 수열 2 (c++)

https://www.acmicpc.net/problem/12015

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

 

그리디

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

using namespace std;

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

	int N;
	cin >> N;

	/*
		가장 긴 증가하는 수열 만들기
		앞쪽에 더 큰 수가 없으면 새로운 값을 LIS수열 뒤에 이어붙이고
		더 큰수가 있다면 그 자리를 새로운 값으로 대체한다.
	*/
	vector<int> LIS;
	for (int i = 0; i < N; ++i)
	{
		int num;
		cin >> num;

		// LIS벡터에서 num보다 같거나 큰 수의 위치 찾기
		auto it = lower_bound(LIS.begin(), LIS.end(), num);

		// num보다 같거나 큰 수가 없다면 : LIS의 끝에 num push
		if (it == LIS.end())
		{
			LIS.push_back(num);
		}
		// num보다 같거나 큰 수가 있으면 : num으로 대체
 		else
		{
			*it = num;
		}
	}

	cout << LIS.size();

	return 0;
}

 

 

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

 

지금까지 풀었던 LIS(Longest Increasing Subsequence)문제와 다르게, 이 문제는 수의 제한이 크다.

따라서 2중 반복문을 돌렸다간.. O(1,000,000,000,000) 라는 무시무시한 시간복잡도가 된다.

그래서 그리디로 풀어야 한다.

 

수열 A의 한 요소 A[i]를 LIS에 포함시킬지 말지 판단하려면

어쨌거나 앞서 판단한 숫자들을 다시 돌아보면서 비교해야 하는데,

위에서 수열 A를 다시 돌아볼수 없다는 것을 확인했다.

 

그럼 남은건..

선택한 숫자들을 돌아보는 것이다!

 

 

다음과 같은 로직을 구현하면 된다. 

1. 현재 숫자보다 더 큰수가 있는지 탐색

2. 지금까지의 LIS 일부를 대체할지, 아니면 뒤에 이어붙일지 결정하기. 

// LIS벡터에서 num보다 같거나 큰 수의 위치 찾기
auto it = lower_bound(LIS.begin(), LIS.end(), num);

// num보다 같거나 큰 수가 없다면 : LIS의 끝에 num push
if (it == LIS.end())
{
	LIS.push_back(num);
}
// num보다 같거나 큰 수가 있으면 : num으로 대체
	else
{
	*it = num;
}