[BOJ] 6236. 용돈 관리 (🥈, 이분 탐색)

🔗

풀이

1. 현우의 통장 잔액은 고려할 필요가 없다.
2. 정확히 M번 맞추기 위해 의미없는 입금과 출금을 반복할 수 있으므로 인출 금액이 K일 때 반드시 인출해야 하는 횟수가 M이하면 된다.

K의 초기값이 될 수 있는 값 중에 최소값은 최대 N일과 하루에 쓸 수 있는 최대 금액(10,000원)이다. 대략 10억 정도 되는데 이분 탐색으로 찾게 되면 2^30 정도이기 때문에 30번만 탐색하면 찾을 수 있다.

최대와 최소의 중간 값인 인출 금액 k를 구한 후 해당 인출 금액으로 N일 간 용돈을 썼을 때 인출 횟수가 M을 넘지 않으면 현재 인출 금액은 조건을 만족하므로 최소값을 구하기 위해 다음 탐색은 더 작은 인출 금액 구간에서 시행한다. 최대값을 인출 금액 k 보다 작은 값으로 바꿔주면 된다.

하지만 인출 횟수가 M을 넘게 되면 현재 인출 금액 k가 조건을 만족하지 못해서 더 커져야 한다는 것이므로 더 큰 인출 금액 구간에서 탐색을 수행해야 한다. 이때는 최소값(low)을 k+1 로 변경해야 한다.

탐색을 수행하는 함수 run() 에서는 현재 인출 금액 k가 당일 용돈 cash 보다 작은 경우는 항상 false 를 반환한다. 인출 금액이 용돈 보다 작은 경우는 아무리 인출을 반복해도 소용없기 때문이다.

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

public class Main {
    static final long MAX_N = 100_000;
    static final long MAX_DAY_CASH = 10_000;

    static int N;
    static int M;
    static long[] passbook;

    static boolean run(long K) {
        int count = 1;
        long leftMoney = K;
        for (long cash : passbook) {

            if (cash > K) {
                return false;
            }

            if (cash <= leftMoney) {
                leftMoney -= cash;
            } else {
                leftMoney = K - cash;
                count++;
            }
        }
        return count <= M;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        passbook = new long[N];
        for (int i = 0; i < N; i++) {
            passbook[i] = sc.nextLong();
        }

        long low = 0;
        long high = MAX_N * MAX_DAY_CASH;
        while (low <= high) {
            long k = (low + high) / 2;
            
            boolean result = run(k);
            if (result) {
                high = k - 1;
            } else {
                low = k + 1;
            }
        }

        System.out.println(low);
    }
}