[BOJ] 1654번. 랜선 자르기 & 수 찾기

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

이번 문제는 이분 탐색을 이용해 풀 수 있었습니다. 

이분 탐색은요, 이분동안 탐색을 하는게 아니라 긴 수를 2개로 나누어 탐색하는 방식입니다.

간단한 알고리즘이니 같이 살펴보겠습니다!

[이분 탐색]

1 부터 100까지의 숫자가 있고, 63을 찾는다고 생각해봅시다.

이분 탐색에는 세가지 변수가 필요합니다.

low : 찾는 수 중 제일 작은 수
High : 찾는 수 중 제일 큰 수
mid : 찾는 수 중간에 있는 수

예시를 들면서 설명이 더 쉬울 것 같습니다.

변수 선언 단계에서, 위 조건에 따라 low=1, high=100, mid=50입니다.

low=1

2

...

49

mid=50

51

...

high=100

우리가 찾고 싶은 수는 63입니다. 62는  mid보다 큰 수 이므로 high는 냅두고 low를 51로, mid를 다시 51과 100의 중간 값 76으로 놓습니다.

low=51

52

...

75

mid = 76

77

...

high=100

63는 mid 왼쪽에 있습니다. 이번에는 high를 75로, mid를 51과 75의 중간 값 63으로 바꿉니다.

low=51

52

...

62

mid = 63

64

...

high=75

원하는 수를 찾았습니다! 

다음 문제를 풀어보며 이분 탐색에 대한 감을 익혀봅시다.

www.acmicpc.net/problem/1920

1920번: 수 찾기

이분탐색으로 접근한 풀이법은 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, n_field[100010] = { 0, };
void binary_search(int low, int high, int m);

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int m, m_input;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> n_field[i];
	}
	sort(n_field, n_field + n);

	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> m_input;
		binary_search(0, n, m_input);
	}
	return 0;
}

void binary_search(int low, int high, int m)
{
	while (low <= high)
	{
		int mid = (low + high) / 2;

		if (n_field[mid] == m)
		{
			cout << 1 << "\n";
			return;
		}
		if (n_field[mid] < m)
		{
			low = mid + 1;
		}
		else if(m <= n_field[mid])
		{
			high = mid - 1;
		}
	}

	cout << 0 << "\n";
	return;
}

[이분탐색 적용시켜보기 - 예제와 함께]

이제 이분탐색을 어떻게 써야하는지 알 것 같습니다. 근데, 이 문제에 어떻게 적용시켜야 할까요?

 

처음 이 문제를 접했을때, 처음 떠올린 것은 브루트 포스알고리즘이었습니다.

1부터 자르다보면 언젠가는 랜선의 길이를 찾을 수 있을 것 같은데,,, 1부터 시작하는 여정은 너무나 길고도 긴 길이었습니다. 시간초과가 뻔한 해결방법이었지요. 

 

그래서 우리는 이분탐색을 적용시켜 볼 것입니다. 예제와 함께 전략을 세워보겠습니다.

[예제 입력]
k=4 n=11
802
743
457
539

low = 1, high는 가장 큰 숫자인 802, mid는 1+802의 중간 숫자인 402로 생각해봅시다.

 

길이가 402인 랜선을 만든다고 가정합시다.

802에서는 2개

743에서는 1개

457에서는 1개

539에서는 1개 만들수 있습니다.

우리는 11개의 랜선을 만들고 싶은데, 5개밖에 못만들었군요. 그럼 랜선의 길이를 줄여볼까요?

 

low는 그대로 1, high를 401, mid를 401+1의 중간 값인 201로 생각해봅시다.

 

길이가 201인 랜선들을 만든다면,

802에서는 4개

742에서는 3개

457에서는 2개

539에서는 2개를 만들수 있습니다.

와우, 11개를 잘 만들어 냈습니다!

 

그럼 코드와 함께 살펴보겠습니다.

 

[이분탐색 적용시켜보기 - 코드와 함께]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	long long k, n;
	long long lan[10010] = { 0, };
	long long low, mid, high, ans;

	cin >> k >> n;

	for (int i = 0; i < k; i++)	cin >> lan[i];

	sort(lan, lan + k);

	low = 1;
	high = lan[k - 1];
	ans = high;

	while (low <= high)
	{
		mid = (low + high) / 2;

		long long cnt = 0;
		for (int i = 0; i < k; i++)
		{
			cnt += lan[i] / mid;
		}

		if (cnt >= n)
		{
			low = mid + 1;
			ans = mid;
		}
		else
		{
			high = mid - 1;
		}
	}
	cout << ans;
	return 0;
}

sort 함수를 써서 high값을 얻는 모습을 보실 수 있습니다.

while문 내부의 for문에서 각 랜선들을 순회하며 mid로 나눠 잘려진 랜선의 갯수를 cnt에 더하는 모습을 볼 수 있습니다.