[백준,c++] 6236번 - 용돈 관리

문제

6236번: 용돈 관리

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, max_money;
vector<int> v;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>M;
    
    for(int i=0; i<N; i++){
        int inp; cin>>inp;
        v.push_back(inp);
        max_money += inp;
    }
    int ans = 0;
    int start = 1, end = max_money; // 최대 인출 금액은 모든 날의 이용할 금액을 합한 값이다.
    
    while(start <= end){
        bool flag = false;
        int take_cnt = 1;
        int mid = (start + end) / 2;
        int money = mid;
        int temp_money = money;
        
        for(int i=0; i<v.size(); i++){
            if(v[i] > temp_money){
                take_cnt++;
                temp_money = money;
            }
            temp_money -= v[i];
            if(temp_money < 0){
                flag = true;
                break;
            }
        }
        if(flag || take_cnt > M) start = mid + 1;
        /*
            아래 조건을 추가하면 틀림
            2 2
            100 200
            와 같은 부분에서 225를 출력하는데 더 작은 값을 찾을 수 있음에도 불구하고 종료하기 때문
         else if(take_cnt == M){
             cout<<money;
             break;
         }
         */
        else{
            ans = money;
            end = mid - 1;
        }
    }
    cout<<ans;
}

 

풀이

1원 ~ 모든 날의 이용할 금액을 합한 값 사이의 값인 K를 이분 탐색을 통해서 찾아, 그 K의 값만큼 인출했을 때 주어진 조건을 만족하는지 탐색하면 됩니다.

K의 값을 찾는 이분 탐색 O(logN) * 이용할 금액 비교 O(N) = O(NlogN) 안에 탐색이 가능합니다. 

다만 코드에도 주석으로 써 놨다 시피 take_cnt == M과 같은 조건을 통해 break 시키면 정답이 올바르지 않은데 그 이유는

2 2
100 200
와 같은 입력일때 225에서 K탐색을 종료하는데, 200이라는 더 작은 값을 찾을 수 있음에도 끝내기 때문입니다.