[백준] #6236. 용돈 관리 (실버 2)

https://www.acmicpc.net/problem/6236

 

1. 이진탐색 대상 → 출력값인 최소 인출 금액

2. 최소인출금액을 구하려는데 그에 대한 기본 low와 high값은? (인출 횟수 상관없이!)

• low : 입력받은 값들 중 가장 큰 값
  
  
• high :  모든 입력값들 더한 값

3. 인출횟수는 어떻게 고려?
    ㄴ mid값을 인출금액으로 했을 때 인출이 몇번 필요한지 계산해본 후 

• 인출해야하는 횟수보다 mid값을 사용해 계산해본 인출횟수가
  • 많으면 : 인출을 더 많이 해야하는 것이기 때문에 인출금액이 지금보다 더 커져야 함 → low = mid + 1
  • 적으면(같으면) : 인출횟수가 덜 필요한 것이기 때문에 인출금액을 지금보다 줄여야 함 → high = mid - 1
    (주어진 인출금액으로 모든 과정을 처리할 수 있는 경우 현재 크기가 가능한 최소 인출횟수라고 간주
      → minMoney = mid)

 

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 = 0;
		int sum = 0;
		for (int i = 0; i < n; i++) {
			money[i] = Integer.parseInt(br.readLine());
			min = Math.max(min, money[i]);
			sum += money[i];
		}


		int low = min;
		int high = sum;
		int minMoney = 0;

		while (low <= high) {
			int mid = (low+high) / 2;
			int num = 1;
			int total = mid;
			for (int mon : money) {
				if (total < mon) {
					num++;
					total = mid;
				}
				total -= mon;
			}


			if (num > m) {
				low = mid + 1;
			}  else {
				minMoney = mid;
				high = mid - 1;
			}
		}
		System.out.println(minMoney);

	}
}