백준 1654 - 랜선 자르기 (C++/이분 탐색/Binary Search)

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

접근법

이진 탐색 문제이다.

랜선의 길이를 받고, 원하는 개수가 될때까지 이분탐색을 진행해주면 된다.

 

예제입력인 아래를 확인해보자

4 11

802

743

457

539

 

이 경우, 랜선의 길이를 200으로 자른다 가정했을때

802 길이의 랜선에서 4개

743 길이의 랜선에서 3개

457 길이의 랜선에서 2개

539 길이의 랜선에서 2개

해서 총 11개, 두 번째로 입력한 11을 충족한다.

 

만약 랜선의 길이를 100으로 자르면  

802 길이의 랜선에서 8개

743 길이의 랜선에서 7개

457 길이의 랜선에서 4개

539 길이의 랜선에서 5개

로 입력받은 11개보다는 많이 만들지만, 최대값은 아니다.

 

만얀 랜선의 길이가 201로 자르면

802 길이의 랜선에서 3개 (802 / 201 = 3, 나머지 199)

743 길이의 랜선에서 3개

457 길이의 랜선에서 2개

539 길이의 랜선에서 2개

이므로, 랜선을 10개밖에 만들지 못한다.

 

위 예제에서 최적의 길이는 200이다.

 

그럼 문제를 풀 알고리즘을 선택해보자.

위 예제는 최대값이 802라 Brute Force로 하나하나 다 탐색해도 될 것 같지만, 최대 랜선의 길이가 2^31 - 1 에 개수가 10000개 까지 입력을 받을 수 있다.

시간초과가 뜰게 눈에 보이므로, 여기선 이진 탐색으로 접근한다.

 

어처피 최대 랜선의 길이는, 가장 긴 랜선의 길이를 넘지 못하므로 (위 예제에선 802) 이 값을 high 로 두고, 1을 low로 둔다음 

이진탐색을 진행하면 된다.

 

(이진 탐색의 알고리즘은 아래 위키피디아 링크를 참조

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

)

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

 

몇 가지 주의할 예시

최소 값

5 5

1

1

1

1

1

(만약 low 값이 0부터 탐색한다면, 위 예시를 충족하지 못한다. 랜선의 길이는 0이 될 수 없을 뿐더러,  만약 0으로 둔다해도 (0 + 1) / 2값은 0이므로 무한루프에 걸린다)

 

최대 값 초과

4 4

2147483647

2147483647
2147483647
2147483647  

 

2^31 - 1 은 2,147,483,647이다. 이는 int의 max값에 아슬아슬하게 걸쳐 될거같지만, 중간에 더하고 빼는 과정에서 int형으로 변수 선언시 overflow가 날 수도 있다. 메모리 제한이 엄청나게 빡빡한 문제가 아니니 맘편히 long long으로 설정했다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int N, cntLAN;
	cin >> N >> cntLAN;

	vector<int> vec;
	long long max = 0;

	for (int i = 0; i < N; i++)
	{
		int length;
		cin >> length;
		vec.push_back(length);
		if (max < length) max = length;
	}
	
	long long low = 1;
	long long high = max;
	long long ans = 0;
	while (low <= high)
	{
		long long mid = (low + high) / 2;
		int cnt = 0;
		for (int v : vec)
		{
			cnt += (v / mid);
		}
		if (cnt >= cntLAN)
		{
			low = mid + 1;
			ans = mid;
		}
		else
		{
			high = mid - 1;
		}
	}

	cout << ans;
	return 0;
}