문제
N개의 강의를 순서대로 M개의 블루레이에 녹화한다. 각 블루레이의 크기가 동일할 때, 가능한 블루레이의 최소 크기를 구하라.
입력
첫째 줄에 N, M이 주어지고, 둘째 줄에 N개의 강의 길이가 주어진다.
출력
블루레이의 최소 크기를 출력한다.
예제
| 입력 | 출력 |
|---|---|
9 3 1 2 3 4 5 6 7 8 9 | 17 |
풀이
매개 변수 탐색(Parametric Search)으로 블루레이 크기를 이분 탐색한다.
- 탐색 범위: 하한은 가장 긴 강의 길이, 상한은 모든 강의 합(10억)이다
- 중간값 mid를 블루레이 크기로 가정하고, 필요한 블루레이 수를 계산한다
- 강의를 순서대로 담되 mid를 초과하면 새 블루레이를 시작한다
- 필요한 블루레이 수가 M 이하이면 크기를 줄이고, 아니면 늘린다
핵심 아이디어: "크기 X로 M개 이하에 담을 수 있는가?"라는 결정 문제를 O(N)에 판별하고, 이를 이분 탐색으로 최적화한다.
코드
import java.io.*;
import java.util.*;
public class Day363BOJ2343기타레슨 {
static int N, M;
static int[] A;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int L = -1, R = 1000000000, ans = 0;
for (int i = 0; i < N; i++)
L = Math.max(L, A[i]);
while (L <= R) {
int mid = (L + R) / 2;
if (determination(mid)) {
R = mid - 1;
ans = mid;
} else {
L = mid + 1;
}
}
System.out.println(ans);
}
static boolean determination(int value) {
int cnt = 1, sum = 0;
for (int i = 0; i < N; i++) {
if (sum + A[i] > value) {
sum = A[i];
cnt++;
} else {
sum += A[i];
}
}
return cnt <= M;
}
}복잡도
- 시간: O(N log S) - S는 강의 길이 합, 각 판별에 O(N)
- 공간: O(N)