43. 뮤직비디오
인프런의 it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 수강하여 공부한 내용을 기록한 포스트입니다. 문제는 공개하지 않습니다.
풀이과정
이분검색을 응용하는 문제이다. 처음 문제를 보고 DP나 Brute Force를 사용하는건가 싶어서 막막했는데 아니었다 ㅠㅠ
이분검색을 이용하는 결정 알고리즘이라고 한다.
- 주어진 입력 내에서 가능한 최대 녹화 길이를 찾는다.
1 ~ 1,000*10,000 - 이분검색을 통해 가능한 녹화 길이를 결정한다.
코드
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<int> arr(n);
int sum = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
sum += arr[i];
}
int left = 1, right = sum, mid;
int partial_sum, min=sum, partial_cnt;
while (left <= right) {
mid = (left + right) / 2;
partial_sum = 0;
partial_cnt = 1;
for (int i = 0; i < n; i++) {
if (partial_sum + arr[i] <= mid) {
partial_sum += arr[i];
}
else {
partial_sum = arr[i];
partial_cnt++;
}
}
if (partial_cnt <= m) {
min = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
printf("%d\n", min);
return 0;
}
REFERENCE