2352_반도체 설계_그리디 알고리즘

문제

  반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

  예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

입력

  첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력

  첫째 줄에 최대 연결 개수를 출력한다.

---

문제 해결

  자기보다 높은 숫자가 자기한테 할당된 숫자보다 높은 수를 갖고 있으면 꼬인다. 즉, 자기 숫자보다 높은 위치에 있는 숫자들중 할당된 숫자가 높은 친구들만 살아남음.

  처음에는 단순하게 O(N^2)의 풀이를 생각하였지만, 시간초과로 인해 틀렸었음. 다른 이들의 풀이를 보던 와중에 LIS라는 알고리즘을 발견하게 되었고 다른이의 풀이를 참고하여 적용하였음. lower_bound

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX	40001

using namespace std;

int n, len = 1, large = 0;
int v[MAX];
int dp[MAX];

int main(void) {
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> v[i];
	}
	dp[len] = v[1]; // 초기값 설정
	
	for(int i = 2; i <= n; i++) {
		if(dp[len] < v[i]) {
			dp[++len] = v[i];
		}
		else {
			int val = lower_bound(dp + 1, dp + len + 1, v[i]) - dp;
			dp[val] = v[i];
		}
	}
	cout << len << endl;
	return 0;
}