6236. 용돈 관리

문제

[BOJ-6236] 용돈 관리

---

문제 해결 아이디어

인출 금액 K에 대해 이진 탐색, check 함수로 M번 이내 인출 가능 여부 판단!

조건

• 정확히 M번 인출 (부족하면 강제, 남아도 선택적으로 재인출 가능)
• 하루치 금액보다 K가 작으면 불가능
• 최소 인출 횟수 ≤ M 이면, 나머지는 임의로 재인출하여 M번 맞출 수 있음

이진 탐색 접근

• 탐색 범위: l = max(pay[i]) ~ r = sum(pay[i])
  • 최소: 하루치는 감당해야 하므로 최댓값
  • 최대: 한 번에 전부 뽑는 경우
• 최소 K 탐색 → check(mid) 참이면 ans = mid, 더 작은 값 탐색 (r = mid - 1)

check 함수

• K원으로 시작, 잔액이 당일 금액보다 부족하면 재인출 (cnt++)
• 최종 인출 횟수 cnt ≤ M 이면 가능

---

코드

import java.util.*;
import java.io.*;

public class BOJ_6236 {
    static int N;
    static int M;
    static int[] pay;
    static int sum = 0;
    static int max = 0;

    private static boolean check(int k) {
        int cnt = 1;
        int remain = k;

        for (int i = 0; i < N; i++) {
            if (remain < pay[i]) {
                cnt += 1;
                remain = k;
            }
            remain -= pay[i];
        }
        return cnt <= M;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        pay = new int[N];

        for (int i = 0; i < N; i++) {
            pay[i] = Integer.parseInt(br.readLine().strip());
            sum += pay[i];
            max = Math.max(max, pay[i]);
        }

        int l = max;
        int r = sum;
        int mid = (l + r) / 2;
        int ans = 0;

        while (l <= r) {
            if (check(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
            mid = (l + r) / 2;
        }

        System.out.println(ans);
    }
}

---

예제 풀이

• N=7, M=5
• pay = [100, 400, 300, 100, 500, 101, 400]
• max = 500, sum = 1901
• 이진 탐색 범위: l=500, r=1901

---

K=500 으로 check 시뮬레이션

날	지출	잔액	인출 횟수
1일	100	500 → 400	1
2일	400	400 → 0	1
3일	300	부족 → 재인출, 500 → 200	2
4일	100	200 → 100	2
5일	500	부족 → 재인출, 500 → 0	3
6일	101	부족 → 재인출, 500 → 399	4
7일	400	부족 → 재인출, 500 → 100	5

cnt = 5 ≤ M(5) → 가능

이진 탐색으로 K=500보다 작은 값도 탐색하지만 모두 불가능 → ans = 500