[백준 알고리즘][BOJ][C++] 이분 탐색(binary search) - 1365번 꼬인 전깃줄

안녕하세요~

 

이번시간에는 1365번 꼬인 전깃줄 문제를 풀어보려고 합니다.

 

www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

 

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

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

​

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

 

문제

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

출력

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

 

예제 입력 1

4
2 3 4 1

예제 출력 1

1

정답 코드

#include <iostream>
#include <stdio.h>
#define INF 123456789
using namespace std;

int map[100000];
int sum[100000];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		sum[i] = INF;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &map[i]);
	}

	sum[0] = map[0];
	for (int i = 1; i < n; i++)
	{
		int left = 0;
		int right = n;
		int mid;
		while (left <= right)
		{
			mid = (left + right) / 2;
			if (sum[mid-1] < map[i] && sum[mid] > map[i]) break;
			if (sum[mid-1] < map[i])
			{
				left = mid + 1;
			}
			else
			{
				right = mid - 1;
			}
		}
		sum[mid] = map[i];
	}
	int answer;
	for (answer = 0; answer < n; answer++)
	{
		if (sum[answer] == INF) break;
	}
	printf("%d\n", n - answer);
}