[백준 알고리즘][C++] 이분 탐색(binary search) - 2352번 반도체 설계

안녕하세요~

​

이번시간에는 2352번 반도체 설계 문제를 풀어보려고 합니다.

 

www.acmicpc.net/problem/2352

2352번: 반도체 설계

 

명심하셔야 될 것은 일단 문제를 풀기 전에 코딩을 먼저 시작하지 마시고, 반드시 연습장으로 생각을 정리하고! 이 후에 생각이 맞는 것 같다고 확신이 되면 그 때 코딩을 시작하세요. 코드를 작성하면서 문제를 풀게되면 정리가 안된 상태기 때문에 코드 수정이 잦아지고, 정신이 없어지게 됩니다ㅠㅠ

그러니 반드시 노트에 어떻게 풀 것인지에 대한 정리를 다 하시고 코딩을 시작하시기 바랍니다!!

​

binary search 공부에 좋은 문제입니다.

 

문제

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

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

입력

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

출력

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

코드

#include <stdio.h>
#include <iostream>
#include <string.h>

using namespace std;

int wire[40001];
int sum[40001];
int c[40001];

#define ARRAY_SIZE(A) sizeof(A)/sizeof(A[0])


// Binary search (note boundaries in the caller)
// A[] is ceilIndex in the caller
int CeilIndex(int A[], int l, int r, int key)
{
	while (r - l > 1)
	{
		int m = l + (r - l) / 2;
		if (A[m] >= key)
			r = m;
		else
			l = m;
	}
	return r;
}

int LongestIncreasingSubsequenceLength(int A[], int size)
{
	// Add boundary case, when array size is one

	int *tailTable = new int[size];
	int len; // always points empty slot

	memset(tailTable, 0, sizeof(tailTable[0])*size);

	tailTable[0] = A[0];
	len = 1;
	for (int i = 1; i < size; i++)
	{
		if (A[i] < tailTable[0])
			// new smallest value
			tailTable[0] = A[i];

		else if (A[i] > tailTable[len - 1])
			// A[i] wants to extend largest subsequence
			tailTable[len++] = A[i];

		else
			// A[i] wants to be current end candidate of an existing
			// subsequence. It will replace ceil value in tailTable
			tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i];
	}

	delete[] tailTable;
	return len;
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		sum[i] = 1;
		scanf("%d", &wire[i]);
	}

	int max = LongestIncreasingSubsequenceLength(wire, n);
	printf("%d\n", max);
}