문제
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.
강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.
강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.
출력
첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.
풀이
내용이 뭔가 길고 복잡해서, 예를 들면 다음과 같다.
9 3 <== n, m
1 2 3 4 5 6 7 8 9 <== 각 강의의 길이블루레이를 m개 즉 3개로 만들고 싶다. 숫자를 높이라고 치면 동일한 높이의 박스 3개에 숫자들을 집어넣고 싶다. 이때, 숫자들이 박스의 크기를 넘어서서는 안된다.
박스 크기가 15라고 하면, 1 2 3 4 5, 6, 7, 8, 9로 분배하여 나눌 수 있다. 박스가 4개 생성됐으므로 m을 만족시키지 못한다.
그러므로 박스의 개수는 줄여야하는데 어떻게 줄일까?
박스의 크기가 커지면 박스의 개수는 줄어들고, 박스의 크기가 작아지면 필요한 박스의 개수는 늘어난다.
즉 원하는 박스의 크기를 찾아야 한다.
박스의 크기를 설정해서 m을 만족시키는지 여부를 판단하면서 박스 크기를 조절해가면 된다.
이 크기를 찾아가는 과정을 이진 탐색을 이용해서 한다.
반례들이 몇 개 있었는데 바보같이 헷갈렸다.
ex)
9 4
9 9 9 9 9 9 9 9 9
answer = 27아 그냥 생각을 못해서 9 9 9 3개씩 3박스밖에 생성이 안되는데 어떻게 27이 나오지? 라고 생각했다.
(9, 9) (9, 9) (9, 9) (9, 9, 9) 로 네 박스 나온다.
그렇담 26은?
(9, 9) (9, 9) (9, 9) (9, 9) (9) 로 5박스가 되므로 m을 만족하지 않는다.
27부턴 3도 4도 만족시키므로 최소한의 상자 크기가 되는 것이다.
코드 로직에서는 알아서 이런 부분이 처리가 되긴 한다.
이진탐색에 필요한 parameter start와 end의 초기값은
start는 입력 받은 값들 중 가장 큰 값 <-- 그렇지 않으면 아예 담을 수도 없는 경우가 발생
end는 m이 1일 경우 하나의 박스에 모든 값을 담아야하므로 모든 값들의 합이 된다.
그렇게 start와 end로 탐색을 진행해 나가면 된다.
풀이 코드 python
n, m = map(int, input().split())
lessons = list(map(int, input().split()))
start = max(lessons)
end = sum(lessons)
result = 10e9
def bs(start, end):
global result
#print("start = {}, end = {}".format(start, end))
if start > end:
return
mid = (start+end) // 2
sum = 0
cnt = 0
for i in lessons:
if sum + i > mid:
cnt += 1
sum = i
continue
sum += i
cnt += 1 # sum에 값이 남아있으므로 박스가 하나 더 필요하다.
if cnt > m:
#print("cnt > m")
bs(mid+1, end)
elif cnt < m:
if result > mid:
result = mid
bs(start, mid -1)
bs(start, end)
print(result)풀이 코드 java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class boj2343 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
int n = Integer.parseInt(stk.nextToken());
int m = Integer.parseInt(stk.nextToken());
int[] arr = new int[n];
int start = 0;
int end = 0;
stk = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(stk.nextToken());
if (arr[i] > start) start = arr[i];
end += arr[i];
}
while (start <= end) {
int mid = (start + end) / 2;
int sum = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum > mid) {
cnt++;
sum = arr[i];
}
}
cnt++; // sum에 값이 남아있기 때문에 박스가 하나 더 필요하다.
if (cnt > m) {
start = mid + 1;
}
else
end = mid - 1;
}
System.out.println(start);
}
}