[백준] 알고리즘 C++ 1654번 - 랜선 자르기문제

문제

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

1654번: 랜선 자르기

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <limits.h>
using namespace std;
long long arr[10001];
int k, n;
void binnary_search() {
	long long left = 1, right = LLONG_MAX-1;
	long long max = 0;
	while (left<=right) {
		long long mid = (left + right) / 2;
		long long temp = 0;
		for (int i = 1; i <= k; i++) {
			temp+= (arr[i]/mid);
		}
		if (temp >= n) {
			left = mid + 1;
			if (mid > max) {
				max = mid;
			}
		}
		else {
			right = mid - 1;
		}
	}
	cout << max;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	 
	cin >> k >> n;
	for (int i = 1; i <= k; i++) cin >> arr[i];
	binnary_search();
	
}

해설

자를 랜선의 길이를 정해서 이미 가지고 있는 랜선에서 자를때 자를 수 있는 개수가 주어졌을 때 최대로 자를 수 있는 랜선의 길이를 구해야한다.

그렇다면 1~21억이되는 숫자의 랜선길이를 다 해보면 좋겠죠?

하지만 이는 너무 비현실적이니 이분탐색을 통해 중간지점에서 결과값을 확인하고 계속해서 반으로 줄여나가면서 경우의 수를 조금 줄여봅시다.

나누어진 개수가 N보다 크거나 같을 때 mid값을 조금 올려서 n에 근접하게 합니다.

나누어진 개수가 N보다 작을때는 mid값이 너무 크다는 이야기닌깐 미드값을 줄여주기 위해 오른쪽 값을 mid -1로 설정해줍니다.

문제는 이분탐색으로 해결하면 쉽게해결 할 수 있습니다.

또한 int로 하면 실패가 뜨니 long long으로 해결하면 됩니다.