문제
K개의 랜선이 있고, 각각 길이가 다르다. 이 랜선들을 모두 동일한 길이로 잘라서 N개 이상의 랜선을 만들고자 한다. N개를 만들 수 있는 랜선의 최대 길이를 구한다.
입력
- 첫째 줄: 보유 랜선 수 K와 필요한 랜선 수 N (1 이상 10,000 이하)
- 이후 K개의 줄: 각 랜선의 길이 (1 이상 2^31-1 이하)
출력
- 자를 수 있는 최대 랜선 길이
예제
| 입력 | 출력 |
|---|---|
4 11 802 743 457 539 | 200 |
풀이
"특정 길이로 잘랐을 때 N개 이상 만들 수 있는가?"를 판별 함수로 삼아 매개 변수 탐색(이분 탐색)으로 최대 길이를 구한다.
- 탐색 범위를
min = 0,max = 최대 랜선 길이 + 1로 초기화한다. mid = (min + max) / 2로 중간값을 구한다.- 각 랜선을
mid로 나눈 몫의 합(cnt)을 계산한다. cnt < N이면 길이가 너무 길므로max = mid, 아니면 길이를 늘릴 수 있으므로min = mid + 1로 범위를 좁힌다.- 반복이 끝나면
min - 1이 답이다. (오버플로 방지를 위해long타입 사용)
핵심 아이디어: 랜선 길이가 커질수록 만들어지는 개수가 단조 감소한다는 성질을 이용한다. 이분 탐색으로 "N개 이상 만들 수 있는 최대 길이"를 O(K log X) 시간에 찾는다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day78BOJ1654랜선자르기 { // 랜선 자르기
static int N, K;
static int[] arr;
static long min = 0, mid = 0, max = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] st = br.readLine().split(" ");
K = Integer.parseInt(st[0]);
N = Integer.parseInt(st[1]);
arr = new int[K];
for (int i = 0; i < K; i++) {
arr[i] = Integer.parseInt(br.readLine());
max = Math.max(arr[i], max);
}
max++;
while (min < max) {
mid = min + (max - min) / 2;
long cnt = 0;
for (int i = 0; i < K; i++)
cnt += (arr[i] / mid);
max = cnt < N ? mid : max;
min = cnt < N ? min : mid + 1;
}
System.out.println(min - 1);
br.close();
}
}복잡도
- 시간: O(K log X) — X는 최대 랜선 길이, 이분 탐색 log X회 × K개 합산
- 공간: O(K) — 랜선 길이 배열