6236번. 용돈 관리

 

아이디어

임의의 K 원에 대해서 최소 인출 횟수가 M 보다 크면 K 가 너무 작다는 뜻이고 M 보다 작으면 K 가 너무 크다는 뜻이다.

 

따라서 K 원에 대해서 최소 인출 횟수를 계산해서 M 보다 크면 K 를 늘려가고 M 보다 작으면 K 를 줄여가는 방법을 사용하면 된다.

 

그리고 문제에서는 최소 금액 K 를 요구하고 있으므로 K == M 을 만족하는 케이스에서도 K 를 줄여가는 방식을 통해 K == M 을 만족하는 최소 K 를 구하면 된다.

 

추가로 현우가 주머니에 소지할 수 있는 금액의 최대값이 K 이므로 K 는 i번째 날에 이용할 금액들 중 최대값 이상이어야 한다. 그리고 인출 횟수인 M 의 최소값이 1이므로 K 가 가질 수 있는 최대값은 이용할 금액들의 합이되어 아래와 같은 범위를 가진다.

 

max(이용 금액)  ≤  K  ≤  sum(이용 금액)

 

 

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] money = new int[N];
        int start = 1;
        int end = 0;
        for (int i = 0; i < N; i++) {
            money[i] = Integer.parseInt(br.readLine());
            start = Math.max(start, money[i]);
            end += money[i];
        }

        while (start <= end) {
            int K = (start + end) / 2;

            int balance = 0;
            int cnt = 0;

            for (int i = 0; i < N; i++) {
                if (balance < money[i]) {
                    cnt++;
                    balance = K;
                }
                balance -= money[i];
            }

            if (cnt <= M) {
                end = K - 1;
            } else {
                start = K + 1;
            }
        }

        System.out.println(end + 1);
    }
}