6236번-용돈관리

문제

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

6236번: 용돈 관리

---

접근방법

https://hyeophyeop.tistory.com/6 백준의 기타레슨과 매우 유사한 문제입니다.

mid값을 어떻게 잡는가가 핵심이었던 문제였는데 저는 "현우가 당일날 사용할 수 있는 금액"으로 기준을 삼고 left값과 right값을 결정하였습니다.

left값은 현우가 당일 사용하는 금액이 기준치보다 작으면 안됩니다. 왜냐하면 인출금액 K를 최소화하기로 했기 때문입니다. 그래서 left 값은 주어진 비용값중 가작 큰 걸 설정하였고 right값은 모든 비용들을 합하여 최대 범위를 설정하였습니다.

이 문제도 m의 범위로 인해 cnt를 1로 설정하고 시작하여야 합니다.

---

정답코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 1e5 + 1;
int n, m;
ll arr[MAX];
 
int main(void)
{
    fastio;
    cin >> n >> m;
 
    ll maxValue = 0;
    ll lowValue = 0;
    for(int i =0; i < n; i++)
    {
        cin >> arr[i];
        lowValue = max(lowValue, arr[i]);
        maxValue += arr[i];
    }
 
    ll left = lowValue;
    ll right = maxValue;
    ll ans;
    while(left <= right)
    {
        ll mid = (left + right) / 2;
 
        ll cnt = 1, sum = 0;
        for(int i = 0; i < n; i++)
        {
            if(sum + arr[i] > mid)
            {
                cnt++;
                sum = 0;
            }
            sum += arr[i];
        }
 
        if(cnt <= m)
        {
            right = mid - 1;
            ans = mid;
        }
        else
            left = mid + 1;
    }
    cout << ans <<"\n";
}