백준 - 반도체 설계 (2352) [C++]

이 문제는 이분 탐색을 이용해서 푸는 문제이다.

 

이 문제는 일단 입력이 최대 40,000 이므로 O(N log N) 이하의 알고리즘으로 풀 수 있다.

 

이 문제의 핵심은 이 문제가 LIS (Longest Increase Subsequence) 문제임을 파악하는 것이다. 나는 이걸 파악하지 못해 검색을 통해 알게 되었다.

 

입력 예시를 보면

6
4 2 6 3 1 5

와 같은데, 꼬이지 않는 최대의 선 개수이므로 2, 3, 5를 고르면 된다. 이 형태가 최장 증가 수열이므로 LIS를 구하면 된다.

 

LIS는 두 가지 방법이 있는데, 하나는 DP를 이용해서 푸는 방법이고 다른 하나는 이분 탐색을 이용해서 푸는 방법이다.

 

DP를 이용할 때에는 dp[i] = i번째 값을 포함한 최장 증가 수열의 길이로 놓고 이중 루프를 돌며 풀면 된다.

그러므로 DP는 O(N^2)의 시간이 걸리고, 이는 이 문제에서 쓸 수 없다.

 

이분 탐색을 이용할 때에는 좀 더 간단한데, LIS 배열 (벡터) 를 준비한 다음 입력 값들을 루프를 돌면서 LIS 배열의 맨 뒤보다 현재 값이 크면 그냥 집어넣고, 작거나 같을 경우에 lower_bound를 통해 들어갈 위치를 찾고 값을 갱신해주면 된다.

 

루프를 돌면서 이분 탐색을 하므로, O(N log N) 시간이 소요된다. 따라서 해당 방법으로 이 문제를 풀면 시간 안에 풀 수 있다.

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

using namespace std;

#define MAX 40000

int n;
int arr[MAX];

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;

		arr[i] = temp;
	}

	vector<int> lis;
	lis.push_back(arr[0]);

	for (int i = 1; i < n; i++) {
		if (lis.back() < arr[i]) {
			lis.push_back(arr[i]);
		}
		else {
			int index = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
			lis[index] = arr[i];
		}
	}

	int answer = lis.size();

	cout << answer << '\n';

	return 0;
}