백준 6236번
https://www.acmicpc.net/problem/6236

문제

---

생각하기

---

• 이분 탐색 문제이다.

  • K(한번에 인출할 값)를 mid로 해서 이분탐색으로 찾아낸다.

동작

    private static boolean check(int referenceAmount) {
        int withdrawCount = 0;
        int nowHaveMoney = 0;

        for (int i = 0; i < N; i++) {
            int todayUsedMoney = arr[i];

            if (todayUsedMoney > referenceAmount) {
                return false;
            }

            if (todayUsedMoney > nowHaveMoney) {
                nowHaveMoney = referenceAmount - todayUsedMoney;
                withdrawCount++;
            } else {
                nowHaveMoney -= todayUsedMoney;
            }
        }

        return withdrawCount <= M;
    } // End of check()

check()에서는 referenceAmount로 이분 탐색으로 결정된 값이 몇 번의 출금이 이루어지는지 확인해서 M보다 클 경우와 작은 경우로 low와 high를 조절한다.

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M, max;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(binarySearch(0, max));
        return sb.toString();
    } // End of solve()

    private static int binarySearch(int low, int high) {
        if (low > high) {
            return low;
        }

        int mid = (low + high) / 2;
        if (check(mid)) {
            return binarySearch(low, mid - 1);
        } else {
            return binarySearch(mid + 1, high);
        }
    } // End of binarySearch()

    private static boolean check(int referenceAmount) {
        int withdrawCount = 0;
        int nowHaveMoney = 0;

        for (int i = 0; i < N; i++) {
            int todayUsedMoney = arr[i];

            if (todayUsedMoney > referenceAmount) {
                return false;
            }

            if (todayUsedMoney > nowHaveMoney) {
                nowHaveMoney = referenceAmount - todayUsedMoney;
                withdrawCount++;
            } else {
                nowHaveMoney -= todayUsedMoney;
            }
        }

        return withdrawCount <= M;
    } // End of check()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max += arr[i];
        }
    } // End of input()
} // End of Main class