가장 긴 증가하는 부분 수열 2 (feat. 백준, 12015번)

가장 긴 증가하는 부분 수열 2
https://www.acmicpc.net/problem/12015

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

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int ans[1000001]{ 0 };
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, index = 1, start, end, mid, chk;
	cin >> N;
	for (register int i = 0, v; i < N; ++i) {
		cin >> v;
		if (ans[index - 1] < v)
			ans[index] = v, ++index;
		else {
			chk = 0;
			start = 1;
			end = index;
			while (end - start >= 0) {
				mid = (end + start) / 2;
				if (ans[mid] < v)
					start = mid + 1;
				else
					chk = mid, end = mid - 1;
			}
			if (chk > 0)
				ans[chk] = v;
		}
	}
	cout << index - 1;
	return 0;
}
// *&)*@*

1. 위 문제는 dp를 사용해서 풀수도 있습니다만 카테고리가 이분 탐색이라 이분 탐색 형태로 풀었습니다.
2. 입력된 값을 하나씩 받아서 배열을 완성합니다.
3. 이때 배열의 마지막값보다 큰값을 받으면 배열에 덧붙이고, 작은 값이라면 만들어진 배열을 이분 탐색하여 입력받은 값과 교체합니다.
4. 위 내용은 '길이' 를 구하는 것이기 때문에 가능합니다. 가령 입력이 [10, 15, 20, 13] 이라면 정답은 [10, 15, 20] 이지만 위 이분 탐색을 통하면 [10, 13, 20] 이 정답이 되게 됩니다.
5. 하지만 '길이' 는 동일하게 3 이므로 정답을 도출할 수 있습니다.