백준 2352(반도체 설계)

www.acmicpc.net/problem/2352

2352번: 반도체 설계

문제를 잘 읽고 생각을 좀 하다보면 n번 포트를 꽂을 차례가 되었을 때, 그 전에 최종적으로 무슨 포트를 어디에 꽂았느냐를 가지고 이게 가능한지 아닌지를 판단할 수 있다. 

 

따라서 가능한 경우에만 갯수를 하나씩 늘려나가면서 저장을 하면 dp로 풀수 있다는 것을 알 수 있다. 

그렇게 dp로 풀 수 있다고 생각을 했지만 입력이 40000이므로 N^2의 전체 확인 알고리즘으로 풀면 시간초과가 난다. 

 

그러면 시간을 어떻게 줄일 수 있을까 

 

아무리 고민을 해도 모르겠어서 구글링을 했다.

 

이러한 dp 대표 문제 중 LIS라는 문제가 있고, NlogN의 방법으로 풀 수 있는 방법이 있다고 한다. 

 

방법은 좀 창의적이다

 

dyngina.tistory.com/16

LIS (Longest Increasing Subsequence)

이 블로그를 참조하면 좋을 것 같다.

 

뭔가 느낌적으로는 설명할 수 있겠는데 구체적인 설명이 어렵다 그냥 블로그 보고 이해하자 

 

그렇게 하면 NlogN의 방법으로 가능하다 

 

아 단점은 실제로 원하는 수열이 어떤 수열인지 알 수 있는 방법이 없다. 그냥 갯수만 구하는 것이다. 이것만 주의하자 

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 40005

int dp[MAX];
int num[MAX];
int n;

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
	}
	int size = 1;
	dp[1] = num[1];
	for (int i = 2; i <= n; i++) {
		if (dp[size] < num[i]) {
			size++;
			dp[size] = num[i];
			continue;
		}
		int idx = lower_bound(dp + 1, dp + 1 + size, num[i]) - dp;
		dp[idx] = num[i];
	}
	cout << size;
}