알고리즘
[Java] 백준 2343번 기타 레슨
J3SUNG
2023. 8. 8. 20:48
728x90
이분 탐색 문제입니다.
N개의 강의를 M개 이하의 블루레이로 녹화할 때 최소 길이를 구해야합니다.
길이를 기준으로 이분탐색을 진행해서 가능한 경우를 찾고
가능하다면 더 짧은 길이가 있는지, 불가능 하다면 더 긴 길이를 탐색하게 하였습니다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int result = 1_000_000_000;
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[n + 1];
int[] prefixSum = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; ++i) {
arr[i] = Integer.parseInt(st.nextToken());
prefixSum[i] = arr[i] + prefixSum[i - 1];
}
int left = 0;
int right = 1_000_000_000;
while (left <= right) {
int mid = (left + right) / 2;
int start = 0;
int sum = 0;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (prefixSum[i] - prefixSum[start] > mid) {
sum = Math.max(sum, prefixSum[i - 1] - prefixSum[start]);
start = i - 1;
++cnt;
}
}
sum = Math.max(sum, prefixSum[n] - prefixSum[start]);
++cnt;
if (cnt > m) {
left = mid + 1;
} else if (cnt <= m) {
result = Math.min(result, sum);
right = mid - 1;
}
}
bw.write(result + "\n");
bw.close();
}
}