[백준]1654 랜선 자르기

jyukki included in 백준

2020-02-26 245 words 2 minutes

Contents

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

풀이:

배열을 받아온다.

배열의 들어있는 랜선의 길이 중 최댓값이

만들 수 있는 최대 길이의 랜선이므로 최댓값을 설정한다.

최솟값은 1로 설정한다.

최댓값과 최솟값의 중간값을 m이라고 하자.

모든 배열의 원소를 m으로 나눈 몫을 모두 더한다.

더한 값이 필요한 랜선의 갯수보다 작다면, m값이 너무 크다는 것이므로 최댓값을 m - 1 로 바꿔준다.

더한 값이 필요한 랜선의 갯수보다 크거나 같다면, 만들 수 있다는 것이므로 답에 저장해 놓는다.

이때, 랜선의 최대 길이를 찾아야 하므로, 랜선의 갯수와 같다고 바로 끝내지 말고 위로 가면서 최댓값을 찾아야한다.

l 을 0으로 설정할 경우 m이 0이 나와 0으로 나누게 되어 런타임 에러가 날 수도 있으니 조심하자.

랜선의 길이가 2^31 - 1 보다 작거나 같으므로 int 보다는 long long 을 사용하자.

코드:

사용언어 : c++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


#include <iostream>
#include <algorithm>
using namespace std;
long long n, k, i, a[10001], sum, m, l = 1, r = 0, c = 0;
int main() {
	cin >> k >> n;
	for (i = 0; i < k; i++) {
		cin >> a[i];
		r = max(r, a[i]);
	}
	while (l <= r) {
		sum = 0;
		m = (r + l) / 2;
		for (i = 0; i < k; i++)
			sum += a[i] / m;
		if (sum < n)	r = m - 1;
		else {
			c = max(c, m);
			l = m + 1;
		}
	}
	cout << c << endl;
	return 0
}