[알고리즘][C++] 뮤직비디오(이분탐색 응용) ; 결정 알고리즘

input: 

9 3

1 2 3 4 5 6 7 8 9

 

그렇다면 답은 1~45 사이에 존재할 것이다! (<-이거를 이분탐색하는 것) 

 

👌 1 ~ 45 

 

23 ? 

 

1+2+3+4+5+6 

7+8 

9

=> 가능! answer=23; (== 23부터 45까지는 전부 가능 -> 더 볼 필요X)

 

👌 1 ~ 22

 

11?

 

1+2+3+4

5+6

7

8

9

 

=> 5개니까 불가능. (== 11이하는 전부 불가능) 

 

 

👌 12 ~ 22

 

17 ? 

 

1+2+3+4+5

6+7

8+9

 

=> 가능! answer=17; 

 

..

.

반복 

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;


int a[1001], n;

int Count(int s){
	int i, cnt=1, sum=0;
	for(i=0; i<n; i++){
		if(sum+a[i]>s){ //실제로 더한 것은 아님  
			cnt++;
			sum=a[i];
		}
		else sum+=a[i];
	}
	return cnt; 
}


int main(){ 
	//freopen("input.txt", "rt", stdin);
	//int n
	int i, m, lt=1, rt, mid, sum=0, answer, cnt, max=-2147000000; 
	
	scanf("%d %d", &n, &m);
	//vector<int> a(n);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
		//sum+=a[i];
		rt+=a[i];
		if(a[i]>max) max=a[i];//반례.. !  
	}
	
	
//	//rt=sum;
//	while(lt<=rt){
//		mid = (lt+rt)/2;
//		sum=0;
//		cnt=1; 
//			
//		for(i=0; i<n; i++){
//			sum+=a[i];
//			if(sum>mid) {
//				sum=a[i];
//				cnt++;	
//			}
//		}
//		
//		if(cnt <= m){
//			rt=mid-1;
//			answer=mid;
//		}
//		else if(cnt>m){
//			lt=mid+1;
//		}
//		
//	} 
	
//===================함수로 작성======================//
	while(lt<=rt){
		mid = (lt+rt)/2;
		if( mid>=max && Count(mid)<=m){
			rt=mid-1;
			answer=mid;
		}
		else lt=mid+1;
		
	} 	
	
	printf("%d", answer);
	
	return 0;
}