BOJ 6236 : 용돈 관리

• 문제 링크 : boj.kr/6236
• 난이도 : S1
• 태그 : 이분 탐색

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> arr(n);
    for(auto &e : arr) cin >> e;

    int l = 1, r = 1e9+1;
    int ans = INF;
    while(l+1 < r) {
        int mid = (l+r)/2;

        int cnt = 1, curr = mid;
        for(auto e : arr) {
            if(e > mid) {
                cnt = INF;
                break;
            }
            if(curr < e) {
                cnt++;
                curr = mid;
            }
            curr -= e;
        }
        if(cnt > m) l = mid;
        if(cnt <= m){
            r = mid;
            ans = min(ans, mid);
        }
    }
    cout << ans;

    return 0;
}

---

풀이

mid를 lo로 할지 hi로 할지 잘 생각해서 풀어야 한다.

mid와 lo의 결과가 같다면 lo = mid, mid와 hi의 결과가 같다면 hi = mid이다.