백준 6236번: 용돈 관리

문제 링크 : https://www.acmicpc.net/problem/6236

6236번: 용돈 관리

 문제 설명 

 

1. 하루에 사용하는 금액과 돈을 인출 할수있는 횟수가 주어진다.

2. 인출 횟수를 꼭 맞추고 하루에 돈 소비량을 맞출수있는 최소 인출금액을 구하면된다 

 

주의사항 : 인출금액은 고정 , 만약 돈이남았는데 오늘 돈 소비량보다 작다-> 돈을 입금후 다시 인출.

 

 알고리즘 

 

이분탐색으로 인출금액을 찾아낸다.

 

최소 인출금액 (lo) : 하루 소비금액중 최대 금액 ; (주의)

hi 는 INF로

while 안을 살펴보면 , 돈을 쓰다가 음수가 나오면  cnt ++ 해서

cnt가 m보다 크다 그럼 lo 를 mid+1 로

cnt가 m보다 작다 그럼 hi 를 mid-1 로.

마지막에 mid 출력.

 

 코드 

#include<iostream>
#include<algorithm>
using namespace std;
 
 
int main() {
    int N, M, lo = 0;
    cin >> N >> M;
    int arr[100001];
    int hi = 0;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        lo = max(lo, arr[i]);
        hi = hi + arr[i];
    }
 
    int mid = 0;
 
    //이분 탐색
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        int cnt = 1;
        int money = mid;
        for (int i = 0; i < N; i++) {
            money = money - arr[i];
            if (money <= 0) {
                money = mid - arr[i];
                cnt++;
            }
        }
 
        if (cnt > M) lo = mid + 1;
        else
            hi = mid - 1;
 
    }
 
    cout << mid;
 
}