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

링크

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

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

해설

어떤 분류의 문제다 라고 딱 설명드리기 어려운 문제입니다.

문제를 푸는 키 알고리즘은 아니긴 한데 lower_bound라는 이분 탐색을 이용해서 위치를 찾긴 합니다.

 

알고리즘은 다음과 같습니다.

1. 입력을 받습니다.

2. 입력받은 값이 현제 리스트의 끝값보다 작거나 같으면 lower_bound를 이용해 찾은 곳에 덮어 씌웁니다.

3. 입력받은 값이 현제 리스트의 끝 값보다 크면 리스트 뒤에 추가합니다.

 

알고리즘만 보면 이게 뭐 하는 건지 싶습니다.

간단하게 설명을 드리자면 배열을 하나 사용하고 증가하는 부분 수열을 계속 덮어 씌우다가

결국 튀어나가면 그때가 최대 크기의 수열인 것입니다.

간단한 예를 들어보겠습니다.

10, 50, 60, 20, 30, 40, 50

위의 예를 알고리즘을 적용하면

3번째인 60까지는 위와 같이 순차적으로 쌓이게 됩니다.

그런데 이때 이 예의 가장 긴 증가하는 부분 수열인 10 20 30 40 50 의 뒷 파트 20 30 40 50 이 들어오는 것을 잘 보시면

 

 

마치 원래 있던 수열 10 50 60 을 덮어쓰는 것처럼 보이게 됩니다.

이게 핵심입니다.

 

이 배열에 계속 후보가 될만한 것들을 덮어 씌우다가 결국 맨 마지막에 수열의 크기를 측정하면

입력에서 나올 수 있는 가장 긴 증가하는 부분 수열이 되는 것입니다.

 

 

모두 코드에 구현되어있습니다.

코드는 배열이 비어있다는 예외를 없애기 위해서 0번째에 가장 작은 값 0을 삽입하였습니다.

배열 대신 vector을 사용해서 구현해도 됩니다.

그러면 정답은 vector.size() - 1 이 됩니다. ( 맨 앞에 0을 넣으므로 )

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int N, TABLE[1000001], idx = 0;

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

	cin >> N;
	TABLE[0] = 0;
	for (int i = 0; i < N; ++i) {
		int temp;
		cin >> temp;

		if (temp <= TABLE[idx])
			*lower_bound(TABLE, TABLE + idx, temp) = temp;
		else
			TABLE[++idx] = temp;
	}

	cout << idx;

	return 0;
}