전에 풀었던 이진탐색문제와 아주 비슷하게 생겨서 보자마자 이진탐색을 이용하면 되겠다고 생각했다. 즉, begin, end 값을 최초에 설정해두고 툭툭 값을 던져보면서 그 범위를 반으로 나눠나가는 방식을 이용했다. N과 레슨의 최대 길이를 고려했을 때 최대 O(log1,000,000,000)의 시간복잡도를 가지기 때문에 가능한 풀이방법이라고 생각했다! 여기서 begin은 블루레이의 크기가 될 수 없는 값 중 가장 큰 값이고 end는 최소 블루레이 크기로 설정했다.
+) 한 레슨의 크기가 블루레이의 크기보다 큰 경우를 꼭 고려해야한다!
import java.util.*;
public class BOJ2343 {
static int n, m;
static int[] numArray;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
numArray = new int[n];
for (int i = 0; i < n; i++) numArray[i] = sc.nextInt();
int begin = 0;
int end = 1000000000;
while ((end - begin) > 1) {
int mid = (begin + end) / 2;
if (isPossibleLength(mid)) end = mid;
else begin = mid;
}
System.out.print(end);
}
private static boolean isPossibleLength(int length) {
int tempSum = 0;
int count = 1;
for (int i = 0; i < n; i++) {
if (numArray[i] > length) return false;
if ((tempSum + numArray[i]) > length) {
tempSum = numArray[i];
if (++count > m) return false;
} else tempSum += numArray[i];
}
return true;
}
}