문제
앞에서 이진 탐색 풀었다고 자신감이 붙었는데, 이진 탐색으로 해결해야 한다는 것을 알고 문제를 봤음에도 어떻게 풀이해나가야 할지 감이 안 잡혔다.
문제 풀이
- 탐색에 사용할 Array를 무엇으로 둘 것인가?!
=>블루레이의 크기 - m 개의 블루레이로 나눌 때, 모든 그룹이 mid(블루레이의 크기)보다 작은 경우를 찾자. 그 중에서도 가장 작은 mid 값을 구하자
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
private static int N, M;
private static int [] arr;
private static int low, high;
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());
arr = new int[N];
st = new StringTokenizer(br.readLine());
// 이진 탐색에서 탐색할 대상 = "블루레이의 크기"
// low: arr에서 가장 긴 동영상 (하나의 영상은 담을 수 있어야 하기 때문에)
// high: arr의 전체 동영상 길이 (하나의 블루레이에 담는 경우)
high = 0;
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
high += arr[i];
low = Math.max(low, arr[i]);
}
binarySearch();
System.out.println(low);
}
private static void binarySearch() {
int mid, sum, count;
while (low <= high) {
mid = (low + high) / 2;
sum = 0; // 한 블루레이에 담아지는 강의의 길이 합
count = 0; // 블루레이의 갯수
for (int i = 0; i < N; i++) {
if (sum + arr[i] > mid) { // mid(블루레이의 크기)를 넘는 순간, 그 전까지의 영상들을 하나의 그룹으로 묶는다.
sum = 0;
count++;
}
sum += arr[i];
}
count++; // 마지막 그룹 추가
if (count <= M) { // M보다 작거나 같은 경우에는, 더 작은 값이 존재할 수 있기 때문에 high를 mid-1로 줄인다.
high = mid - 1;
} else {
low = mid + 1;
}
}
}
}
나는 주어진 배열만을 이진 탐색할 줄 알았지, 내가 이진 탐색을 실행할 데이터를 만들어낼 생각을 못 했다. 항상 이진 탐색 = 배열 이라는 공식처럼 생각하고 있어서 그런 것 같다.
다음에 풀 때는 주어진 값만 사용할 것이라, 어떤 값을 "이진 탐색의 Array"로 사용할까?를 생각해보자!
