이번에는 백준 2343번 기타 레슨 문제를 풀어보았습니다.
처음에는 블루레이를 어떻게 나눌지 직접 결정해야 하는 문제처럼 보였지만, 실제로는 블루레이의 크기를 결정했을 때 필요한 블루레이 개수를 계산할 수 있다는 점을 이용하는 문제였습니다.
따라서 블루레이의 크기를 기준으로 이분 탐색을 수행하여 최소 크기를 구할 수 있었습니다.
문제 설명
N개의 강의가 순서대로 주어집니다.
강의의 순서는 바꿀 수 없으며,
모든 강의를 M개의 블루레이에 담으려고 합니다.
이때 모든 블루레이의 크기는 동일해야 하며,
가능한 블루레이 크기의 최솟값을 구하는 문제입니다.
풀이 아이디어
블루레이의 크기를 하나 정하면,
그 크기로 모든 강의를 담을 때 필요한 블루레이 개수는 쉽게 계산할 수 있습니다.
이를 이용하여
- 현재 크기로 M개 이하의 블루레이만 필요하면 더 작은 크기도 가능한지 탐색
- M개보다 많이 필요하면 블루레이 크기를 늘림
이라는 방식으로 이분 탐색을 수행하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N, M;
int inp[100000];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
long long high = 0;
long long low = 0;
for (int i=0; i<N; i++) {
cin >> inp[i];
if (inp[i] > low)
low = inp[i];
high += inp[i];
}
low--;
while (low + 1 < high) {
long long mid = (high + low) / 2;
long long temp = 0;
int cnt = 1;
for (int i=0; i<N; i++) {
if (temp + inp[i] <= mid) {
temp += inp[i];
}
else {
temp = inp[i];
cnt++;
}
}
if (cnt <= M)
high = mid;
else
low = mid;
}
cout << high;
return 0;
}풀이 흐름
- 탐색 범위를 설정합니다.
- 블루레이 크기를
mid로 정합니다. - 현재 크기로 필요한 블루레이 개수를 계산합니다.
- M개 이하라면 더 작은 크기를 탐색합니다.
- M개보다 많이 필요하다면 크기를 늘립니다.
- 탐색이 끝난 뒤
high를 출력합니다.
구현 포인트
1. 이분 탐색 범위
블루레이 크기의 최솟값은
가장 긴 강의보다 작을 수 없습니다.
따라서
low = 가장 긴 강의 길이으로 설정하였습니다.
코드에서는 반복문의 형태를 맞추기 위해
low--;를 수행하였습니다.
반대로 최댓값은
모든 강의를 하나의 블루레이에 담는 경우이므로
high = 모든 강의 길이의 합으로 설정하였습니다.
2. 필요한 블루레이 개수 계산
현재 블루레이에 강의를 계속 담다가
크기를 초과하면 새로운 블루레이를 하나 사용합니다.
if (temp + inp[i] <= mid)
temp += inp[i];
else {
temp = inp[i];
cnt++;
}이 과정을 끝내면
현재 크기로 필요한 블루레이 개수인 cnt를 구할 수 있습니다.
3. 이분 탐색
현재 크기로
cnt <= M이라면
블루레이를 더 작게 만들어도 가능할 수 있으므로
high = mid;로 탐색 범위를 줄였습니다.
반대로
cnt > M이라면
현재 크기로는 블루레이가 부족하므로
low = mid;를 수행하여 크기를 늘렸습니다.
4. 정답이 high인 이유
반복문은
while (low + 1 < high)형태로 수행됩니다.
탐색이 끝나면
low는 조건을 만족하지 않는 가장 큰 값high는 조건을 만족하는 가장 작은 값
이 됩니다.
따라서 가능한 블루레이의 최소 크기는
high가 됩니다.
5. 시간복잡도
블루레이 크기를 이분 탐색하는 데
O(log(강의 길이의 합))이 걸리고,
각 탐색마다 모든 강의를 한 번씩 확인하므로
O(N)이 필요합니다.
따라서 전체 시간복잡도는
O(N log S)(S는 모든 강의 길이의 합)으로 문제를 해결할 수 있습니다.
