백준 [6236] 용돈 관리 (자바)

문제

풀이

1. 최소 i번째에 사용할 금액들 중 최대 값을 min으로 잡아서 최소 출금 금액을 정한다.
2. max는 모든 money 배열의 금액을 더해서 한 번의 출금으로 남은 N일을 출금없이 보낼 수 있는 금액으로 설정
3. 최소 금액을 구하는 과정
   1. min과 max의 중간 값을 지정하고 sum에 money 배열을 더해가면서 진행
   2. sum > mid인 경우 써야하는 돈이 출금한 금액보다 커서 출금을 해야한다는 의미 -> 출금 진행 withdraw++;
   3. withdraw > M인 경우 출금 금액을 너무 작아서 자주 인출한 것임. 예산(mid)을 늘려야 함 -> min  = mid + 1;
   4. withdraw < M인 경우 출금 금액이 커서 너무 인출을 안함. 예산(mid)를 낮춰야 함 -> max = mid - 1;

정답코드

package com.baekjoon.p6236;

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

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 min = 1, max = 1;
        for (int i = 0; i < N; i++) {
            money[i] = Integer.parseInt(br.readLine());
            min = Math.max(min, money[i]);
            max += money[i]; // 최대 값은 날마다 써야하는 모든 돈의 액수의 총합
        }

        while (min <= max) {
            int sum = 0, mid = (min + max) / 2, withdraw = 1; // 제일 처음 한 번 인출했음을 가정(mid값)

            for (int i = 0; i < N; i++) {
                sum += money[i];

                /**
                 * mid 값(현재 지정된 K원)을 넘으면 인출을 다시 해야함
                 */
                if (sum > mid) {
                    sum = money[i];
                    withdraw++;
                }
            }

            /**
             * 인출 횟수가 M번 보다 많으면 예산을 늘려서 출금을 덜하게 해야함
             * 반대로 인출 횟수가 M보다 적으면 인출 횟수를 맞추기 위해 예산을 줄이기
             */
            if (withdraw > M) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }

        System.out.println(min);
    }
}