[BOJ] 6236번 : 용돈 관리

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

- 시간 제한 : 1초
- 메모리 제한 : 128MB

접근 방법

이 문제는 2343번문제와 매우 유사한 문제입니다. 2343번 문제와 마찬가지로 이진 탐색을 이용하여 해결할 수 있습니다.

인출 금액이 돈을 가장 많이 쓰는 날의 금액보다 크거나 같아야합니다. 그렇지 않으면 아무리 인출을 하더라도 해당 날짜에 금액이 부족하게 됩니다.

static void func() {
    // 적어도 돈을 가장 많이 쓰는 날 이상의 금액을 인출해야 한다.
    // 그렇지 않으면 아무리 인출을 하더라도 금액이 부족하다.
    int left = maxPlan;
    int right = 10_000 * 100_000;

    // 이진 탐색을 이용하여 해답을 찾는다.
    while (right >= left) {
        int mid = (left + right) / 2;

		...
    }

인출 금액을 정했을 때, 필요한 인출 횟수를 구하는 함수는 아래와 같이 구현할 수 있습니다.

static int getWithdrawalCount(int withdrawalAmount) {
    int count = 1;
    int money = withdrawalAmount;

    for (int i : plans) {
        money -= i;

        // 돈이 모자라면 현금을 다시 인출하여 사용
        if (money < 0) {
            ++count;
            money = withdrawalAmount - i;
        }
    }

    return count;
}

getWithdrawalCount와 이진 탐색을 이용하여 아래와 같이 문제를 해결할 수 있습니다.

코드

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

public class Main {

    static int n, m;
    static int[] plans;
    static int maxPlan = 0;
    static int result;

    public static void main(String[] args) {
        input();
        func();
        System.out.println(result);
    }

    static void input() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        plans = new int[n];

        for (int i = 0; i < n; ++i) {
            plans[i] = sc.nextInt();
            maxPlan = Integer.max(maxPlan, plans[i]);
        }

        sc.close();
    }

    static void func() {
        // 적어도 돈을 가장 많이 쓰는 날 이상의 금액을 인출해야 한다.
        // 그렇지 않으면 아무리 인출을 하더라도 금액이 부족하다.
        int left = maxPlan;
        int right = 10_000 * 100_000;

        // 이진 탐색을 이용하여 해답을 찾는다.
        while (right >= left) {
            int mid = (left + right) / 2;

            // 지정한 횟수 이하의 횟수만큼 인출해야 할 경우,
            // 인출 금액이 더 적은 경우에 해답이 있는지 탐색해 봐야 한다.
            if (m >= getWithdrawalCount(mid)) {
                result = mid;
                right = mid - 1;
                
            // 지정한 횟수보다 더 많이 인출해야 할 경우,
            // 인출 금액이 더 커야한다.
            } else {
                left = mid + 1;
            }
        }
    }

    /**
     * @param withdrawalAmount 현금 인출 금액
     * @return 돈을 계획대로 쓰기 위해 필요한 인출 횟수
     */
    static int getWithdrawalCount(int withdrawalAmount) {
        int count = 1;
        int money = withdrawalAmount;

        for (int i : plans) {
            money -= i;

            // 돈이 모자라면 현금을 다시 인출하여 사용
            if (money < 0) {
                ++count;
                money = withdrawalAmount - i;
            }
        }

        return count;
    }
}