[백준 6236] 용돈 관리

분류 : 이분 탐색

 

요구사항

효율적으로 돈을 사용하기 위한 최소 금액 구하기

 

풀이

아래 문제 요구사항은 인출하는 경우가 m보다 작으면 okay로 해석할 수 있다.

현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.

 

이분 탐색으로

금액을 정해보고 가능하다면 더 작은 금액을 찾아보고(정답 갱신)

불가능 하다면 더 큰 금액을 찾아서 답을 구한다.

 

 

#include <iostream>

using namespace std;
int n,m;
int map[100100];
bool check(int val){
	int money=val;
	int cnt=1;
	for(int i =0 ; i < n ; i++){
		if(map[i]>val){
			return false;
		}
		//현재 가진거 보다 작다면 현재 가진 돈에서 뺀다

		
		if(money >= map[i]){
			money -=map[i];
		}
		else{
			money = val;
			money -=map[i];
			cnt++;
		}
		
		/*
		if(money - map[i] <0){
			money= val;
			cnt++;
		}
		money -= map[i];
		*/
	}
	if(cnt<=m) return true;
	else return false;

}
int main(){
	scanf("%d%d",&n,&m);
	int sum=0;
	for(int i=0 ; i < n ; i++){
		scanf("%d",&map[i]);
		sum+=map[i];
	}
	int low=0;
	int high=sum;
	int ans=0;
	while(low<=high){
		int mid = (low+high)/2;
		//된다면 더 작을걸 찾아야됨
		if(check(mid)){
			ans=mid;
			high = mid - 1;
		}
		//안된다면 큰 거 
		else{
			low = mid + 1;
		}
	}
	cout<<ans<<endl;
}