[Algorithm]Baekjoon 6236번 :: 용돈 관리

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
int n, m;
int moneys[100001] = { 0 };
 
 
bool check(int withdrawnMoney)
{
    int withdrawnCount = 0;
    int curMoney = 0;
 
    for (int i = 0; i < n; ++i)
    {
        int money = moneys[i];
 
        if (curMoney < money) // 남은돈이 더 적으면
        {
            ++withdrawnCount;
            curMoney = withdrawnMoney - money;
        }
        else
        {
            curMoney -= money;
        }
    }
 
    return withdrawnCount <= m;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    int maxNum = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> moneys[i];
        maxNum = max(maxNum, moneys[i]);
    }
 
    int left = maxNum;
    int right = n  * maxNum ;
    int answer = 0;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (check(mid))
        {
            right = mid - 1;
            answer = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << answer;
}
 
 

 

 

이 문제에서 유의해야할 점은 인출을 할 때는 현재 돈을 전부 다시 입금후에 인출을 해야한다는 것이다.

즉, 만약 현재 300원이 필요한데 100원만 있다면, 100원을 두번 인출하면 되는게 아니라 반드시 300원을 한번 인출해야 한다는 것이다.

 

이렇기 때문에 문제에서 요구하는 최소한의 인출금액은, 주어진 날짜별 금액의 최대값이 된다.

최소한의 인출금액이 날짜별금액보다 작으면 성립이 안된다. 한번밖에 인출못하니까..

그래서 left를 날짜별금액의 최대값으로 맞춰놨다. right는 m이 1일경우 한번의 인출로 모든 날짜의금액을 커버해야되니까 n * maxNum(금액의 최대값)으로 했다.

 

이렇게하고 mid값 (문제에서 요구하는 값)을 이진탐색으로 왔다갔다하면서 끝날짜까지 인출횟수를 카운팅했을 때, m보다 이하이면 return true 시켜주면 된다.

문제에서 m과 반드시 일치하라고 했는데 어차피 횟수가 남으면 그만큼 그냥 인출입금 해버리면 되기때문에 상관없다.