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

백준 2352 반도체 설계

 

2352번: 반도체 설계

 

 

문제 설명

 

 - 반도체 설계 시 n개의 포트를 다른 n개의 포트와 연결해야 한다.

 

 - 왼쪽 그림과 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 연결할 수 없다.

   오른쪽 그림과 같이 연결을 할 경우에는 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 연결할 수 있다.

 

 - 연결선이 꼬이지 않도록 하면서 최대 몇 개까지 연결할 수 있는지 출력하라.

 

---

 

입력 값

 

 - 첫째 줄에 정수 n( 1<= n <= 40,000 )이 주어진다.

 

 - 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호,

   ... n번 포트와 연결되어야 하는 포트 번호가 주어진다.

   이 수들은 1이상 n이하이며 서로 같을 수는 없다

 

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제를 자세히 살펴보면 서로 꼬이지 않고 연결하는 방법은

   a번 포트가 b번 포트에 연결되었을 때 a보다 큰 포트는 b보다 큰 포트에 연결되어야 한다.

 

 - 즉, 1번 포트가 3번 포트에 연결된 경우, 2~n번 포트는 무조건 3번 보다 큰 포트에 연결되어야 한다는 것이다.

 

 - 이것을 정리하면, i번째 포트가 연결되는 포트를 j라고 가정하면, X[i] = j 라고 하자.

    X[i+1] >= j+1이어야한 연결이 가능하다는 것이다.

 

 - 결국 이것이 의미하는 것은 배열 X가 주어졌을 때 점점 증가하는 가장 긴 부분 수열을 찾는 것이다.

 

 - 즉, LIS 문제이다.

최장 증가 부분 수열(Longest Increasing Subsequence)

 

 - N의 최대 크기가 40,000이기 때문에 NlogN의 시간복잡도를 가진 DP + 이분탐색의 LIS를 사용해야 한다. 

 

---

 

 

소스 코드

#include <bits/stdc++.h>

using namespace std;

int arr[400001];
int dp[400001];

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

	int N;
	cin >> N;

	int maxLast = 1;

	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		arr[i + 1] = n;
	}

	dp[1] = arr[1];

	for (int i = 1; i <= N; i++) {

		int start = 1;
		int last = maxLast;
		while (start <= last) {

			int mid = (start + last) / 2;

			if (arr[i] == dp[mid]) {
				start = mid;
				break;
			}
			else if (arr[i] < dp[mid]) {
				last = mid - 1;
			}
			else {
				start = mid + 1;
			}

		}

		dp[start] = arr[i];

		maxLast = max(maxLast, start);
	}

	cout << maxLast << endl;


	return 0;
}