백준 온라인 저지의 2343번 기타 레슨 문제입니다.
[링크] https://www.acmicpc.net/problem/2343
문제 조건과 설명
블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다.
즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다.
이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다.
오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 레슨 동영상을 녹화하기로 했다.
이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.
각 레슨의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.
Input
첫째 줄에 레슨의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다.
다음 줄에는 기타 레슨의 길이가 레슨 순서대로 분 단위로(자연수)로 주어진다.
각 레슨의 길이는 10,000분을 넘지 않는다.
Output
첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.
생각한 아이디어
이분 탐색 문제는 무엇을 탐색할 것인지 생각하는 것이 가장 중요한 것 같습니다.
이 문제는 블루레이의 최소 크기를 찾는 문제입니다.
그리고 조건을 하나씩 살펴봐야 합니다. 이 과정에서 시간이 꽤 걸렸던 것 같습니다.
과정을 하나씩 천천히 살펴보도록 하겠습니다.
먼저, 각 레슨을 블루레이 내에 순서대로 담아야 하는 조건이 있습니다.
그리고 만약 블루레이 크기가 10이었다고 가정해 보겠습니다.
1
2
9 3
1 2 3 4 5 6 7 8 9
이러한 인풋이 들어왔을 때, 앞에서부터 레슨을 더해 봅니다.
1 + 2 + 3 + 4 = 10 입니다. 여기에 5까지 더하면 15가 되어버립니다.
즉, 하나의 블루레이에 1부터 5까지는 들어갈 수 없고, 1부터 4까지만 들어갈 수 있습니다.
그러면 블루레이 1번에 1부터 4까지의 레슨을 담았습니다.
나머지 레슨에 대해서도 진행해 보겠습니다.
5 + 6 = 11이므로, 블루레이 크기를 초과해 버립니다. 따라서 블루레이 2번에는 레슨 5만 들어갑니다.
6, 7, 8, 9 에 대해서도 블루레이 1개에 각각 1개씩만 담기가 가능합니다.
따라서 레슨이 담긴 구성은 다음과 같아집니다.
{1, 2, 3, 4}, {5}, {6}, {7}, {8}, {9} = 총 블루레이 갯수 6개
그런데 인풋에서는 블루레이 갯수가 3개로 주어졌습니다. 즉, 이러한 구성은 답이 될 수 없습니다.
따라서 블루레이 크기를 10이 아니라, 좀 더 늘려야겠다는 결론을 얻을 수 있습니다.
이렇게 임의의 블루레이 크기를 정하여 담아 본 다음, 블루레이 갯수가 인풋에서 제한한 갯수보다 많아지면 블루레이 크기를 늘려야겠고, 적어지면 블루레이 크기를 줄여봐야 겠다는 생각을 할 수 있습니다. 이 부분을 이분탐색하면 됩니다.
이분탐색에서 left, right(low, high)를 정해야 할 텐데, 우선 right(high), 제일 극단적인 끝값은 모든 레슨의 길이를 더한 값이 될 것입니다.
1 2 3 4 5 6 7 8 9 의 인풋을 다 더하면 45입니다. 블루레이 하나의 크기가 45라면, 블루레이 1개에 모든 레슨을 다 담을 수 있습니다.
그러면 맨 왼쪽 끝값은 어떤 값이 되어야 할까요?
블루레이 하나의 크기가 만약 1이었을 경우, 레슨 1만 담을 수 있고 나머지는 모두 담을 수 없습니다.
이러면 문제의 조건에 어긋나게 됩니다. 모든 레슨들을 블루레이에 담아야 하기 때문입니다.
따라서 레슨 중 크기가 가장 큰 9의 값이 왼쪽 끝값이 되어야 할 것입니다.
블루레이 크기가 9라면, 모든 레슨들을 블루레이에 담을 수는 있기 때문입니다.
소스코드
- 초기 low, high 값을 각각 위에서 말한 대로 초기화 하였습니다.
- 이 때 mid = (low + high) / 2 값이 임시로 가정할 블루레이의 크기가 될 것입니다.
- for문을 이용해 모든 레슨들을 하나씩 담아 보면서, 그 합이 mid 값보다 커진다면 필요한 블루레이 갯수를 한개 증가시켜 줍니다. 위에서 말했던 과정들과 동일합니다.
- 그리고 담은 레슨들 말고 그 다음부터 다시 또 담아 보면서 합을 구합니다.
- 이를 끝까지 반복한 뒤, 만약 구한 블루레이 갯수가 M보다 적다면 블루레이 1개당 크기를 줄여야겠고, 블루레이 갯수가 M보다 많다면 블루레이 1개당 크기를 늘려야 할 것입니다.
- 이것이 코드상에서 low = mid+1 이나 high = mid - 1로 조정하는 부분입니다.
- 최종적인 답은 low 에 담겨 있을 것입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
typedef long long ll;
using namespace std;
ll arr[100001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll N, M; // N은 레슨의 수, M은 블루레이의 갯수
cin >> N >> M;
ll sum = 0, low = -1;
for(int i = 0; i < N; i++) {
cin >> arr[i];
sum += arr[i];
low = max(low, arr[i]);
}
ll high = sum;
while (low <= high) {
ll cnt = 0, tempSum = 0;
ll mid = (low + high) / 2;
for (int i = 0; i < N; i++) {
if (tempSum + arr[i] > mid) {
tempSum = 0;
cnt += 1; // 블루레이 갯수 1 증가
}
tempSum += arr[i];
}
if (tempSum != 0) cnt += 1;
// 블루레이 크기로 가정한 mid보다 작아서 1 증가시키지 못했을 경우
// 갯수가 M 이하일 때는, high 값을 줄여본다.
if (cnt <= M) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
cout << low;
return 0;
}