[백준] 용돈 관리

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

6236번: 용돈 관리

이진탐색을 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 현우가 용돈을 사용하는데 계획적으로 사용합니다. 그래서, N일 동안의 지출 계획이 있고, 정확하게 M번만 K원씩 인출하여 사용하려 합니다. 

 

이 때, K의 최솟값을 구해야 합니다. 문제를 한번 읽어보는 것을 추천합니다.

 

<Solution>

통장에서 인출해야 하는 금액 K는 N일간의 지출 계획중 가장 큰 값 보다는 크거나 같아야 하고, N일간의 지출을 모두 더한 값 보다는 작거나 같아야 합니다. 

 

따라서 이렇게 두개의 값을 두고, 이진 탐색을 통해 가능한지 불가능 한지를 판단하면 됩니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
 
using namespace std;
 
#define MAX_N (100000)
 
int N, M;
int need[MAX_N];
 
void Input_Data(void) {
    cin >> N >> M;
    for (int i = 0; i < N;i++) {
        cin >> need[i];
    }
}
 
int find_k(int K){
    int tmp = K;
    int cnt = 1;
    for(int i = 0; i<N; i++){
        if(need[i] <= tmp) tmp-=need[i];
        else{
            cnt++;
            tmp = K;
            tmp-=need[i];
        }
    }
    return cnt;
}
 
int bs(int s, int e){
    int sol = -1;
    while(e>=s){
        int mid = (s+e)/2;
 
        if(find_k(mid)<=M){
            e = mid-1;
            sol = mid;
        }
         
        else{
            s = mid+1;
        }
 
 
    }
    return sol;
 
 
 
}
 
int solution(){
 
    int s=0, e=0;
    for(int i = 0; i<N;i++){
        s = max(s, need[i]);
        e+= need[i];
    }
 
 
    return bs(s,e);
 
 
}
 
int main(void) {
    ios_base::sync_with_stdio();
    cin.tie(nullptr);
    cout.tie(nullptr);
    int sol = -1;
 
    // 입력 받는 부분
    Input_Data();
 
    // 여기서부터 작성
 
    sol = solution();
    // 출력하는 부분
    cout << sol << '\n';
 
    return 0;
}