문제
길이 L인 통나무에 K개의 자르기 지점이 있고, 최대 C번 자를 수 있을 때, 가장 긴 조각의 길이를 최소화하라. 또한 그때의 첫 자르기 위치를 구하라.
입력
첫째 줄에 L, K, C, 둘째 줄에 K개의 자르기 지점이 주어진다.
출력
가장 긴 조각의 최소 길이와 첫 자르기 위치를 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 2 1 3 7 | 7 3 |
풀이
매개변수 탐색으로 "가장 긴 조각이 mid 이하가 되도록 C번 이내로 자를 수 있는가"를 판별한다.
- 자르기 지점을 정렬하고 양쪽 끝(0, L)을 추가한다
- 이분 탐색으로 최대 조각 길이 mid를 결정한다
- 각 mid에 대해 오른쪽부터 그리디하게 자르며 C번 이내인지 확인한다
- 가능하면 mid를 줄이고, 불가능하면 늘린다
핵심 아이디어: 오른쪽부터 자르면 첫 자르기 위치가 가장 작아지며, 매개변수 탐색으로 최적 조각 길이를 O(K log L)에 구한다.
코드
package day799;
import java.io.*;
import java.util.*;
public class Day772BOJ1114통나무자르기 {
static long l;
static int k, c;
static long[] cut;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
l = Long.parseLong(st.nextToken());
k = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
cut = new long[k + 2];
cut[0] = 0;
cut[1] = l;
st = new StringTokenizer(br.readLine());
for (int i = 2; i < k + 2; i++) {
cut[i] = Long.parseLong(st.nextToken());
}
Arrays.sort(cut);
long L = 0, R = l;
long ansWood = l, ansPos = 0;
while (L <= R) {
long mid = (L + R) / 2;
int cnt = 0;
long cutPos = 0;
long len = 0;
for (int i = k; i >= 0; i--) {
len += cut[i + 1] - cut[i];
if (len > mid) {
len = cut[i + 1] - cut[i];
cnt++;
if (len > mid) {
cnt = c + 1;
break;
}
}
}
if (cnt <= c) {
cutPos = cut[1];
if (cnt == c)
cutPos = len;
ansWood = Math.min(mid, ansWood);
ansPos = cutPos;
R = mid - 1;
} else {
L = mid + 1;
}
}
System.out.println(ansWood + " " + ansPos);
}
}복잡도
- 시간: O(K log L)
- 공간: O(K)