[BOJ] 2352 : 반도체 설계

문제 : https://www.acmicpc.net/problem/2352

---

DP LIS BinarySearch

 가장 긴 증가 부분 수열을 구하는 문제로 DP를 이용해 해결할 수 있는데, DP 배열을 BinarySearch를 이용해 채워야한다.

 

Dp[ x ] := 길이가 x 인 증가 부분 수열 중 가장 작은 마지막 값

 

ex )

[ 4 2 6 3 1 5 ] 에서 길이가 2인 증가 부분 수열은 4 - 6 / 4 - 5 / 2 - 6 / 2 - 3 / 2 - 5 / 3 - 5 / 1 - 5 처럼 여러가지가 있지만, 이 중 가장 작은 마지막 값은 3이므로 Dp[2] = 3 이 된다.

 

지금까지 우리가 구한 가장 긴 증가 수열의 길이가 longest 라고 한다면, 우리가 지금 보고 있는 i번 째 값이 Dp[longest] 보다 크다면, 지금까지 구한 longest 길이의 수열의 뒤에 i번 째 값을 이으면 되므로 Dp[longest + 1] 을 갱신할 수 있다. 아니라면, 현재 값을 Dp[ k - 1] < i번 째 값 <= Dp[ k ] 인 곳을 찾아서 갱신하면 된다.(지금까지 구한 부분 증가 수열 중에서 맨 뒤에 값을 이을 수 있는 곳) 이때, Binary Search를 이용해야 시간초과를 해결할 수 있다. 또, 초기값으로 Dp[0] = -INF 로 설정하면 더 간편하게 구할 수 있다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	const int INF = 99999;
	int N;
	cin >> N;

	vector<int> v(N), dp(N + 1, INF);
	for (int i = 0; i < N; i++)
		cin >> v[i];

	// dp[i] := 길이가 i인 증가수열들 중에서 마지막 값 중 최소.
	dp[0] = -INF;
	dp[1] = v[0];
	int longest = 1;
	for (int cur : v) {
		if (dp[longest] < cur) {
			longest++;
			dp[longest] = cur;
		}
		else {
			vector<int>::iterator it = lower_bound(dp.begin(), dp.end(), cur);
			*it = cur;
		}
	}
	int ans = 1;
	for (int i = 1; i <= N; i++)
		if (dp[i] != INF) ans = i;
	cout << ans << '\n';
	return 0;
}

---