https://www.acmicpc.net/problem/2343
해당 문제는 이진 탐색을 활용하는 문제다.
먼저 이진 탐색이 무엇인지 부터 알아보자.
이분 탐색
- 정렬된 데이터에서 원하는 값을 탐색할 때 사용하는 알고리즘
- 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이변서 대상을 찾는다.
- 한 번의 연산에 탐색할 데이터의 크기가 절반씩 줄기 때문에 O(logN)의 시간복잡도를 가진다.
ex) 데이터의 수가 16개라면, 4(log16)번의 연산으로 원하는 값을 찾을 수 있다.
<이분 탐색 과정>
1. 현재 데이터 셋의 중앙값을 선택한다.
2. 중앙값 > 타깃값 : 중앙값 기준으로 오른쪽 데이터셋은 버린다. (중앙값 기준 오른쪽에는 타깃값이 존재하지 않기 때문)
3. 중앙값 < 타깃값 : 중앙값 기준으로 왼쪽 데이터셋은 버린다.
4. 과정 1~3을 반복하다가 중앙값 == 타깃값일 때 탐색을 종료한다.
위 그림은 타깃값은 77, 탐색 범위는 1 ~ 100으로 설정하여 탐색을 진행한 경우이다.
중앙값 50이 77보다 작으므로, 중앙값 기준 왼쪽 데이터셋은 버리고, 오른쪽 데이터셋을 가지고 다시 탐색하는 것을 볼 수 있다.
그럼 이를 바탕으로 문제를 풀어보겠다.
문제에서 M개의 블루레이에 강의를 녹화하겠다고 했고, 이 때 가능한 블루레이의 크기 중 최소를 구하라고 했다.
강의는 중간에 잘리거나 순서가 바뀌면 안 되기 때문에 주어진 순서 그대로 블루레이에 녹화되어야 한다.
여기서 이분 탐색을 어떻게 활용할 것인가?
문제 예제를 통해 생각해보자.
9 3 # N, M
1 2 3 4 5 6 7 8 9녹화할 강의 수는 9개, 강의를 저장할 블루레이 수는 3개이다.
즉, 3개의 블루레이에 / 9개의 강의를 순서대로 녹화할 수 있도록 하는 / 최소의 블루레이 크기를 구하는 것이다.
구하고자 하는 값은 블루레이의 크기이기 때문에, 탐색할 데이터셋도 블루레이의 크기로 이루어져야 한다.
<데이터셋 범위 구하기>
시작값 : 9 (블루레이 크기가 적어도 9는 되어야 모든 강의를 녹화할 수 있기 때문, 이 때 필요한 블루레이의 개수는 6개가 된다.)
끝값 : 45 (모든 강의를 하나의 블루레이에 녹화하겠다고 한다면, 그 때가 블루레이 크기의 최댓값이다.)
따라서 9 ~ 45 사이의 데이터셋을 가지고 이분 탐색을 진행하면 된다.
Code(Python - 오답)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
video = list(map(int, input().split()))
start = max(video)
end = sum(video)
result = sum(video) # 가능한 블루레이 크기 중 최소
while start <= end:
bluSize = (start + end) // 2 # 블루레이 크기
subSize = 0 # 블루레이 하나당 녹화 가능한 비디오 길이
m = 0 # 필요한 블루레이 개수
for size in video:
if subSize + size > bluSize: # 이번 비디오까지 녹화했을 때, 블루레이 크기를 초과한다면,
m += 1 # 블루레이 개수 늘리고,
subSize = 0 # 비디오 개수 초기화(다음 블루레이로 넘어가니까)
subSize += size # 블루레이에 현재 비디오 길이 추가
if subSize != 0: # 남은 비디오가 있다면,
m += 1 # 이 또한 블루레이 하나에 담아야 하므로, 블루레이 개수 추가
if m < M: # 현재 블루레이 크기(bluSize)일 때 필요한 블루레이의 개수가 강토가 녹화하고자 하는 블루레이의 개수(M)보다 작거나 같을 경우,
end = bluSize - 1 # 블루레이의 크기를 줄여야 하므로, end 변경
elif m > M: # 필요한 블루레이의 개수가 강토가 녹화하고자 하는 블루레이의 개수보다 많을 경우,
start = bluSize + 1 # 블루레이의 크기를 늘려야 하므로, start 변경
else: # 필요한 블루레이의 개수가 강토가 녹화하고자 하는 블루레이의 개수와 동일할 경우,
result = min(result, bluSize) # 기존에 저장된 블루레이의 크기와 현재 구한 블루레이의 크기 중 최솟값 저장
end = bluSize - 1 # 현재 구한 블루레이의 크기보다 더 작은 경우가 있을 수 있으므로, end 변경
print(result)
이렇게 제출했으나 오답 처리가 됐다.
문제를 잘못 이해하고 있었다.
M개의 블루레이를 무조건 다 쓰면서 최소의 블루레이 크기를 구하는 줄 알고 마지막 조건문을 작성했는데,
알고 보니 M개 이상만 쓰지 않으면 되는 것이었다.
즉, "M개보다 더 적게 써도 되니까 최소의 블루레이 크기만 구해~" 이다..
이를 반영하여 다시 코드를 짰다.
Code(Python - 정답)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
video = list(map(int, input().split()))
start = max(video)
end = sum(video)
result = sum(video) # 가능한 블루레이 크기 중 최소
while start <= end:
bluSize = (start + end) // 2 # 블루레이 크기
subSize = 0 # 블루레이 하나당 녹화 가능한 비디오 길이
m = 0 # 필요한 블루레이 개수
for size in video:
if subSize + size > bluSize: # 이번 비디오까지 녹화했을 때, 블루레이 크기를 초과한다면,
m += 1 # 블루레이 개수 늘리고,
subSize = 0 # 비디오 개수 초기화(다음 블루레이로 넘어가니까)
subSize += size # 블루레이에 현재 비디오 길이 추가
if subSize != 0: # 남은 비디오가 있다면,
m += 1 # 이 또한 블루레이 하나에 담아야 하므로, 블루레이 개수 추가
if m <= M: # 현재 블루레이 크기(bluSize)일 때 필요한 블루레이의 개수가 강토가 녹화하고자 하는 블루레이의 개수(M)보다 작거나 같을 경우,
result = min(result, bluSize) # 기존에 저장된 블루레이의 크기와 현재 구한 블루레이의 크기 중 최솟값 저장
end = bluSize - 1 # 현재 구한 블루레이의 크기보다 더 작은 경우가 있을 수 있으므로, end 변경
else: # 필요한 블루레이의 개수가 강토가 녹화하고자 하는 블루레이의 개수보다 많을 경우,
start = bluSize + 1 # 블루레이의 크기를 늘려야 하므로, start 변경
print(result)
마지막 조건문만 변경해줬다.
현재 구한 블루레이 개수가 M보다 작더라도 블루레이 크기가 최소가 된다면, 결과값을 바꾸도록 했다.
Code(Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] video = new int[N];
int start = 0;
int end = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
video[i] = Integer.parseInt(st.nextToken());
end += video[i];
start = Math.max(start, video[i]);
}
int result = end;
while (start <= end) {
int bluSize = (start + end) / 2;
int subSize = 0;
int m = 0;
for (int size : video) {
if (subSize + size > bluSize) {
m++;
subSize = 0;
}
subSize += size;
}
if (subSize != 0) {
m++;
}
if (m <= M) {
result = Math.min(result, bluSize);
end = bluSize - 1;
} else {
start = bluSize + 1;
}
}
System.out.println(result);
}
}