[이분 탐색] 백준 2343 기타 레슨

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

 

길이(mid)를 정해두고, 만약 이 길이를 넘거 같아지면 새로운 블루레이 cd에 길이를 저장하는 방식으로 풀었습니다.

	#include <iostream>
	#include <algorithm>
	#define MAX_SIZE 100000
	using namespace std;
	
	int main(){
		int n, m;
		int arr[MAX_SIZE] = {0};
		int left = 0, right = 0;
		cin >> n >> m;
		
		for(int i = 0; i < n; i++){
			scanf("%d", &arr[i]);
			left = max(left,arr[i]);
		}
		right = 1000000000/m;

		
		while(left +1< right){
			int mid = (right + left) /2;
			int sum = 0, cnt = 0;
			
			for(int i = 0; i < n; i++){
				
				if(sum + arr[i]>= mid){
					cnt++;
					sum = 0;
				}
				sum += arr[i];
			}
			
			if(sum!=0) cnt++;
			
			if(cnt <= m) right = mid;
			else		left = mid;
		}
		
		
		
		cout << left;
		
	}