[BOJ, 백준 알고리즘]1654번 문제/ 랜선 자르기

문제

문제 링크

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

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

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

입력

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

출력

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

접근방향

N개의 같은 길이의 랜선을 만들 수 있다는 조건을 만족하는 최대의 랜선 길이 X를 구해야 한다. X의 값을 바꿔가면서 대입해 조건을 만족하는지 확인하면서 만족하는 경우들 중 최대값을 가지는 X를 구해야 한다. 이때 가능한 모든 X의 범위는 [1, max(K)]이다.

처음부터 끝까지 모든 경우를 탐색하는 경우 시간 복잡도는 O(K^2)이며, 문제의 조건에 따라 시간 초과가 발생할 수 밖에 없다. 시간을 절감하기 위해서는 이진 탐색을 이용해야 한다. 이 경우 시간 복잡도는 O(Klog(K))이다.

X가 특정값일 때 랜선의 개수를 N과 비교하여 이진탐색을 해줘야한다. 다만 보통의 이진탐색 문제와는 달리 랜선의 개수가 N개인 X를 구하면 이 값을 바로 반환하는 것이 아니고 가능한 계속 탐색하여 조건을 만족하는 값들 중에서 최대값을 찾아야 한다.

 

풀이

X의 초기 범위를 [1, max(K)]로 잡고 이진탐색을 시작한다.

1. 두 범위의 중간값 maxLen을 잡고 K의 각 원소들을 maxLen으로 나눈 값의 합 sum을 계산한다. sum은 X = maxLen 일 때 생기는 랜선의 개수이다.
2. 이제 sum을 N과 비교하여 sum이 더 작을 경우, 왼쪽 범위를 같은 방법으로 다시 탐색한다.
3. sum이 N보다 더 크거나 같을 경우, 오른쪽 범위를 마찬가지로 다시 탐색한다. 이 부분이 이 문제가 특이한 점이다.(보통은 같은 값을 찾으면 탐색을 종료함)
4. 범위의 왼쪽 끝값이 오른쪽 끝값보다 크거나 같은 경우 까지 이를 반복하며 탐색이 종료된 뒤에 범위의 오른쪽 끝값을 반환한다.
5. 이진 탐색에서 반환한 값이 문제의 답이다.

 

이 문제를 풀 때 주의할 점들이 몇 가지 있다.

• 이진 탐색 과정에서 변수들이 int형의 범위를 초과하는 경우가 나온다. 이 경우 오버플로우가 일어나 값이 왜곡되므로 long long형을 써야한다.
• 처음에 X에 대해 이진 탐색을 시행할 때 탐색 범위는 1부터 시작해야한다. 특정 X에서 랜선의 개수를 구하는 과정에서 0으로 나눗셈을 하여 런타임 에러가 일어날 수 있다.
• 이거는 아직 이유를 완전히 이해를 하지 못했는데 이진 탐색을 통해 반환해야하는 X의 값은 maxLen이 아닌 범위의 오른쪽 끝값이다. 이것 때문에 한참을 막혀있었다.

소스 코드

언어는 C++ 사용

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

using namespace std;

long long binarySearch(vector<long long>& input, long long start, long long end, int target){
	long long maxLen = (start+end)/2;
	long long sum = 0;
    //이진 탐색 시행
	while(start<=end){
		sum = 0;
		maxLen = (start+end)/2;
		for(int i=0;i<input.size();i++){
			sum += input[i]/maxLen;
		}
        	//sum이 target보다 작으면 오른쪽 절반 범위 탐색
			if(target>sum){
				end=maxLen-1;
			}
            //sum이 target보다 크거나 같으면 왼쪽 절반 범위 탐색
			else if(sum>=target){
				start=maxLen+1;
			}
	}
	return end;
}

int main() {
	int num, targetNum = 0;
	long long sum = 0;
	vector<long long> abc;
	scanf("%d %d",&num, &targetNum);
	getchar();
	for(int i=0;i<num;i++){
		long long temp = 0;
		scanf("%lld ",&temp);
		abc.push_back(temp);
		sum += temp;
	}
	//이진탐색을 위한 정렬
	sort(abc.begin(),abc.end());
	printf("%lld",binarySearch(abc, 1, abc[abc.size()-1],targetNum));
	return 0;
}