공부 자료/알고리즘
(C/C++) 백준 2343번 - 기타 레슨
뚜루뚜루세니
2021. 7. 29. 20:04
728x90
문제출처: https://www.acmicpc.net/problem/2343
2343번: 기타 레슨
강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
1. 코드
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int les[100001];
int N, M;
bool find(int mid) {
int cnt = 1; //블루레이 수
int sum = 0;
for (int i = 0; i < N; i++) {
if (les[i] > mid) {
return false;
//곡 하나가 녹음시간보다 길 수 없
}
sum += les[i];
if (sum > mid) {
sum = les[i];
cnt++;
}
}
return M >= cnt;
}
int main() {
scanf("%d %d", &N, &M);
int sum = 0;
for (int i = 0; i < N; i++) {
scanf("%d",&les[i]);
sum += les[i]; //모든 레슨의 합
}
int left =1;
int right = sum;
int result = 0;
while (left <= right) {
int mid = (left + right) / 2; //최대 녹음 시간
if (find(mid)) {
result = mid;
right = mid - 1;
}
else
left = mid + 1;
}
printf("%d", result);
}
|
cs |
2. 해결과정
전형적인 이분탐색 문제. right에 곡들의 길이 합으로 두고, mid는 최대 녹음 시간으로 가정.
반복문을 돌려서 레슨의 길이를 더해주는데 더한 값이 mid보다 크면 cnt값이 하나 증가한다.
블루레이수인 m보다 cnt가 크다면 left를 늘리고, 같거나 작으면 right를 줄인다.
3. 느낀점
하면 할 수록 어려운 이분탐색...
728x90