[BOJ/6236번용돈관리] c++ / binary_search

문제

N일 동안 K원을 M번만 인출할 때, 나올 수 있는 K값 중 가장 작은 수를 구하는 문제

 

생각

문제 이해를 잘 못하겠어서 구글링해서 이해했음

하루에 쓸 돈이 mid 값을 넘어가면 안됨

 

문제풀이

1.현우가 가진 돈을 합산함

2.st = 1, en = 1번 과정에서 나온 수

3.st <= en 일 동안, mid = ( st + en ) / 2

3.money[i]가 mid 보다 크다면, ck = 1 break 

4.money[i]가 total 보다 크다면, total = mid,  cnt++ | 한번 인출함

5.total -= money[i] 쓴 금액 차감해줌

6.만약 ck = 1 이거나, cnt < M 일 경우, st = mid + 1; 더 큰 금액을 탐색

6-1.그렇징 않을 경우, result = mid; en = mid - 1; 더 적은 금액을 탐색

7.result 값 출력

 

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int N, M, K, cnt=0, st=1, en = 0, total=0, ck=0, result=0;
int money[1000001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for ( int i = 0; i < N; i++ ) {
        cin >> money[i];
        en += money[i];
    }

    while( st <= en ) {
        int mid = ( st + en ) / 2;

        total = mid;
        cnt = 1;
        ck = 0;
       
        for ( int i = 0; i < N; i++ ) {
            if ( money[i] > mid ) {
                ck = 1;
                break;
            }
            if ( money[i] > total ) {
                total = mid;
                cnt++;
            }
            total -= money[i];
        }
        if ( ck || cnt > M )
            st = mid + 1;
        else {
            result = mid;
            en = mid - 1;
        }
    }
    cout << result;
}