백준 2352 반도체 설계 C++

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

2352번: 반도체 설계

지난 번에 어떤 문제를 이분 탐색으로 풀려다가 자꾸 실패해서 다르게 풀었었는데 그래서 이분 탐색 문제를 하나 더 풀었습니다. 

 

반도체들이 어떻게 하면 가장 많이 연결할 수 있을 지 구하는 문제입니다.

해당 문제는 최장 부분 수열 구하는 문제와 동일합니다.

예를 들어 주어진 그림과 같이 1-4 / 2-2 / 3-6 / 4-3 / 5-1 / 6-5 와 같이 연결되어 있다면 연결 끝부분만 살펴보면 다음과 같습니다.

4 2 6 3 1 5 => 여기서 겹치거나 꼬이지 않으려면 앞선 연결번호보다 다음 연결은 반드시 큰 번호여야 합니다.

그렇기 때문에 2 3 5 이렇게 3개를 연결할 수 있습니다. 그러므로 이는 최장 부분 수열 길이를 구하는 문제와 동일합니다.

 

dp 배열을 dp[i] = "길이가 i인 최장 부분 수열의 마지막 번호 중 가장 작은 값" 으로 정의하겠습니다.

이렇게 잡고 포트 번호가 하나 씩 들어오면서 해당 포트 번호보다 작은 값 중 가장 큰 값을 이분 탐색으로 dp 배열에서 찾으면 dp 배열은 오름차순으로 정렬이 됩니다. 그러므로 계속해서 이분탐색을 진행할 수 있습니다. 

dp[i] 값이 초기화 값 0이면 새로운 포트 번호를, 다른 포트 번호가 할당되어 있다면 기존 값과 새 값 중 작은 값을 가지면 됩니다.

 

그러므로 이와 같습니다.

 

dp[i] = "길이가 i인 최장 부분 수열의 마지막 번호 중 가장 작은 값"

=> dp원소 중 new port num보다 작은 값 중 가장 큰 값 = t 

=> if dp[t의 index+1] == 0 : dp[t의 index+1] = new port num

=> else : dp[t의 index+1] = min(dp[t의 index+1], new port num) 

 

코드는 다음과 같습니다.

(이분탐색할 때 이상한데다 ; 을 하나 더 찍어놔서 계속 무한루프 돌았다. 이거 찾는다고 1시간 걸렸다. ㅠㅜㅠ)

#include<iostream>
#include<algorithm>

using namespace std;

int n;
int ans;
int port[40001];
int dp[40001]; 
// 부분 수열의 길이가 i인 것 중 가장 작은 마지막 값
// ex . 5 2 6 1 8 3 4 7
// 각 위치를 끝점으로 계산했을 때 가장 긴 부분수열 길이
//      1 1 2 1 3 2 3 4
// dp={ 1,3,4,7 } (1부터 index 시작) => 오름차순으로 정렬됨

void init()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int num;
		cin >> num;
		port[i] = num;
		dp[i] = 0;
	}
	ans = 0;
}

int Binary(int start, int last, int num)
{
	// dp 중에서 num보다 작은 가장 큰 값의 인덱스 구하기
	// dp는 오름차순
	int mid = (start + last) / 2;
	while (start <= last) {
		mid = (start + last) / 2;
		if (num > dp[mid]) {
			start = mid + 1;
		}
		else
			last = mid - 1;
	}
	return last;
}

void calculate()
{
	dp[1] = port[1];
	ans = 1;
	int start = 1;
	int last = 1;
	for (int i = 2; i <= n; i++) {
		// 부분 수열 길이 1인 경우
		// 이분 탐색으로 찾을 수 없는 경우
		if (port[i] < dp[1]) {
			dp[1] = port[i];
		}
		else {
			last = ans;
			int idx = Binary(start, last, port[i]);

			// 새로운 최장 부분 수열
			if (dp[idx + 1] == 0) {
				dp[idx + 1] = port[i];
				ans++;
			}
			// 같은 길이 있는 경우
			else {
				dp[idx + 1] = min(dp[idx + 1], port[i]);
			}
		}
	}
}

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

	init();
	calculate();
	cout << ans;
}