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

문제 요약

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

<제한시간: 1초>

문제 분류

• 이분 탐색
• 가장 긴 증가하는 부분 수열: o(n log n)

문제 풀이

가장 긴 증가하는 부분 수열(이하 LIS)문제를 O(nlogn)안에 해결하는 것이 목적이다. 여기서는 이분 탐색을 활용하여 풀었다.
어떠한 벡터 v를 선언하여, LIS의 규칙을 만족시키게 한다. 그리고 인덱스를 살펴보면서 입력의 배열 원소가 들어갈 위치를 탐색하여 삽입한다. 이에 v는 반드시 오름차순으로 정렬되어 있어야 할 것이다. 그리고 v의 크기가 곧 LIS가 된다.
현재 배열을 차례로 탐색하는데, 탐색 중인 원소를 in이라고 하자. in은 v를 참고하여 삽입 위치를 결정한다. 가령, in이 v의 최대값보다 클 경우 맨 뒤로 삽입한다. 그 외의 경우에는 오름차순으로 정렬된 v에서 in보다 크거나 같은 최소의 값을 in으로 대치한다.
가령 v의 원소가 차례로 {1, 5, 10}이라고 가정하고, in의 값이 3이라 하면, v를 {1, 3, 10}으로 변경한다.
in의 삽입 위치는lower_bound()를 사용하여 이분 탐색으로 구해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> v;

int main()
{
	int n, in;

	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		auto t = lower_bound(v.begin(), v.end(), in);
		if (t != v.end()) *t = in;
		else v.push_back(in);
	}
	cout << v.size();

	return 0;
}