[Algorithm] C++ 뮤직비디오(이분검색)

입력설명

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다. 다음 줄에는 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다. 부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.

출력설명

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다

첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요

 

입력예제

9 3 

1 2 3 4 5 6 7 8 9

 

출력예제

17

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>

using namespace std;
int a[1001], n;

int Count(int s) {
	int i, cnt = 1, sum = 0;
	for (i = 1; i <= n; i++) {
		if (sum + a[i] > s) {
			cnt++;
			sum = a[i];
		}
		else {
			sum = sum + a[i];
		}
	}
	return cnt;
}

int main() {
	int m, i, lt = 1, rt = 0, mid, res;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		rt = rt + a[i];
	}
	while (lt <= rt) {
		mid = (lt + rt) / 2;
		if (Count(mid) <= m) {
			res = mid;
			rt = mid - 1;
		}
		else {
			lt = mid + 1;
		}
	}
	printf("%d\n", res);
	return 0;
}