(C++) - 백준(BOJ) 6236번 : 용돈 관리

www.acmicpc.net/problem/6236

6236번: 용돈 관리

이분탐색 문제였습니다. 문제 지문에 오해의 소지가 있어 푸는데 애먹었습니다..

 

풀이방법

* k원을 인출했다면 해당 돈이 부족해질 때까지 다음날에도 그 다음 날에도 계속해서 쓸 수 있습니다. 돈이 부족해졌다면 기존에 있는 돈은 넣고 다시 k원을 인출하므로 k원이 됩니다. 

 

 1. 인출할 돈을 최소로 하기위해 0원부터 0x3f3f3f3f까지 이분탐색을 위해 범위를 정합니다.

 

 2. 매번 mid마다 체크함수를 실행해줍니다.

   모든 날을 확인하면서 현재 가지고 있는 돈이 떨어질 때까지 현재 돈에서 해당 날에 사용한 돈을 빼줍니다. 돈이 떨어졌다면 인출횟수를 1씩증가시켜줍니다. 그 후 인출횟수 <= m이면 true, 아니라면 false를 반환합니다.

 

 3. 체크함수 반환값이 true라면 인출 횟수를 늘려야 하므로 인출금액을 더 줄일 수 있습니다. false라면 인출금액을 늘려줍니다. 인출금액을 늘려준다면 더욱 여러 날에 거쳐 사용할 수 있기 때문에 인출횟수가 감소합니다. 

 

 4. 답을 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,m;
int money[100001];

bool ck(int mid){
    int curMoney = 0;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(money[i] > mid) return false;
        if(curMoney - money[i] < 0) curMoney = mid, cnt++;
        curMoney -= money[i];
    }
    return cnt <= m;
}

int binarySearch(){
    int l = 0;
    int r = 0x3f3f3f3f;
    int ans = 0x7f7f7f7f;

    while(l<=r){
        int mid = (l+r)/2;
        
        if(ck(mid))
            ans = mid,r = mid - 1;
        else l = mid + 1;
    }

    return ans;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> money[i];
    cout << binarySearch();
}