BOJ 3745 - 오름세

문제 링크

문제#

주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다.

정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다.

n일 동안의 주가를 p₁, p₂, ..., pₙ이라고 했을 때, 오름세란 부분수열 pᵢ₁ < pᵢ₂ < ... < pᵢₖ (i₁ < i₂ < ... < iₖ)을 말한다.

n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오.

입력#

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N <= 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. 주가는 한 개 이상의 공백으로 구분되어 있으며, 그 외의 위치에서도 자유롭게 나올 수 있다. 주가는 100,000보다 작거나 같은 자연수이다.

출력#

각 테스트 케이스에 대해서 입력으로 주어진 주가의 가장 긴 오름세의 길이를 출력한다.

풀이#

이 문제는 사실상 가장 긴 증가하는 부분 수열 2와 같은 유형이다. 수열을 앞에서부터 보면서 현재까지 만들 수 있는 증가 부분수열의 후보들을 관리하면 된다.

핵심은 부분수열을 전부 직접 탐색하면 시간 초과가 난다는 점이다. N이 최대 100000이기 때문에 매 원소마다 선형 탐색을 하면 $O(N^2)$가 되어 버린다. 그래서 LIS 배열을 유지하면서 새 값이 가장 뒤 값보다 크면 뒤에 붙이고, 그렇지 않으면 이분 탐색으로 들어갈 위치를 찾아 교체해야 한다.

이 교체 과정은 “해당 길이의 증가 부분수열이 가질 수 있는 가장 작은 끝값”을 유지하는 역할을 한다. 실제 부분수열 자체를 저장하지는 않지만, 길이 정보는 정확하게 보존된다. 따라서 각 테스트 케이스를 $O(N \log N)$에 해결할 수 있다.

코드#

#include <iostream>
#include <vector>
using namespace std;
 
int N;
vector<int> vec;
 
int solve() {
	vector<int> LIS(N);
	LIS[0] = vec[0];
	int ans = 1;
 
	for (int i = 1; i < N; i++) {
		if (vec[i] > LIS[ans - 1]) {
			LIS[ans++] = vec[i];
		}
		else {
			int left = 0;
			int right = ans - 1;
			
			while (left <= right) {
				int mid = (left + right) / 2;
				if (vec[i] > LIS[mid]) left = mid + 1;
				else right = mid - 1;
			}
 
			LIS[left] = vec[i];
		}
	}
 
	return ans;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	while (cin >> N) {
		vec.assign(N, 0);
		for (int i = 0; i < N; i++)
			cin >> vec[i];
		cout << solve() << '\n';
	}
	
	return 0;
}

복잡도#

• 시간 복잡도: $O(N \log N)$
• 공간 복잡도: $O(N)$

마무리#

겉보기에는 단순한 증가 부분수열 문제지만, 제한 때문에 이분 탐색을 곁들인 LIS 풀이가 사실상 정답이다.