[C/C++ 백준 6236번] 용돈 관리 (Silver 3)

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

6236번: 용돈 관리

인출하는 돈의 양을 1~1000000정도 범위로 설정해 놓고, 이분 탐색을 이용해 문제를 해결하자.  while 문 내부에 구현할 시뮬레이션에서 현재 가지고 있는 돈와 인출 조건을 만족시키면서 M보다 작은 cnt를 계속 찾으면 쉽게 해결할 수 있다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int N, M, Money[100001], maxi=-1;
	scanf("%d %d",&N,&M);
	for(int i=0; i<N; i++){
		scanf("%d",&Money[i]);
		maxi = max(Money[i], maxi);
	}
	int left = maxi, right = 1000000, mid, save, money, cnt;
	while(left <= right){
		money = 0;
		cnt = 0;
		mid = (left + right)/2;
		for(int i=0; i<N; i++){
			if(money < Money[i]){
				money = 0;
				money += mid;
				cnt++;
				money -= Money[i];
			}
			else{
				money -= Money[i];
			}
		}
		if(cnt<=M){
			save = mid;
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
	}
	printf("%d",save);
}