[1654] 랜선 자르기

---

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 

요즘 문제 이해하는 시간도 오래 걸린다 ..

K = 4, N = 11, 갖고 있는 랜선의 길이가 차례로

802
743
457
539

라면!

 

이미 있는 4개의 랜선을 동일한 크기로 다 쪼개면 랜선의 개수가 N개 이상이 되어야 함.

// 802 : 200 200 200 200 2
// 743 : 200 200 200 143
// 457 : 200 200 57
// 539 : 200 200 139

// 200개 총 11 개

 

랜선의 길이를 200으로 했을 때 11개,  즉 N개의 랜선을 만들 수 있다.

그리고 200이 랜선 길이의 최댓값이기 때문이 답이 되는 것이다.

 

 

그럼 랜선 길이의 범위를 알아보자.

근데 나와있다. 2^31-1(2,147,483,647)보다 작거나 같은 자연수(0은 포함X)이다.

근데 다 탐색하면 시간이 너무 아까우므로 입력받은 랜선들의 길이 중 최댓값을 랜선 길이의 최대 범위로 설정하자

그러면 우리는 1 ~ max(A)에서 자를 수 있는 랜선 최대 길이를 구하면 된다.

 

 

구하는 과정은 쉬운데, 자료형 범위 설정에서 조금 헤맸다.

이분 탐색으로 구했는데, key를 설정하는 과정에서 overflow가 발생했다.

long long int key = (start + end) / 2; // start랑 end 더해서 int의 범위를 넘어갈 수 있으므로 long long

start와 end는 int로 설정했는데 key를 long long int 으로 설정해서 이미 (start + end)에서 overflow가 났다.

그러므로 start와 end도 long long 으로 자료형을 맞춰줘야 한다.

 

 

나머지는 주석으로 자세히 적어놓았다.

#include <iostream>
using namespace std;

int N, K;
int A[1000000];
int maximum = -1;
// 802 : 200 200 200 200 2
// 743 : 200 200 200 143
// 457 : 200 200 57
// 539 : 200 200 139

// 200개 총 11 개


// 랜선 길이의 범위는? 0 ~ 2^31 -> 0 ~ max(A)


void BinarySearch(long long int start, long long int end) { // 안 하면 key 부분에서 오버플로우가 나는 듯
	if (start > end) return;

	long long int key = (start + end) / 2; // start랑 end 더해서 int의 범위를 넘어갈 수 있으므로 long long

	long long int cnt = 0;
	bool is_success = false;
	for (int i = 0; i < K; i++) {
		cnt += A[i] / key; // 랜선의 길이가 최대 2^31-1이므로 key가 최소일 때 cnt에서 overflow 발생 가능. 그러므로 cnt가 long long
		if (cnt >= N) { // N개 이상으로 많이 만들면
			is_success = true;
			break; // 나가
		}
	}

	if (is_success) {
		maximum = (key > maximum) ? key : maximum; // 최댓값 갱신
		BinarySearch(key + 1, end); // 더 최대 길이 있는지 key보다 큰 범위에서 찾아봄
	}
	else { 
		BinarySearch(start, key - 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> K >> N; // 이미 K개가 있는데 N개의 랜선이 필요함

	int maxi = -1;
	for (int i = 0; i < K; i++)
	{
		cin >> A[i];
		maxi = (A[i] > maxi) ? A[i] : maxi;
	}

	BinarySearch(1, maxi); // 1부터 maxi까지 탐색

	cout << maximum;
}