[ BOJ ][JAVA][6236] 용돈관리

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

6236번: 용돈 관리

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	5737	1861	1314	30.145%

문제

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

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

예제 입력 1 복사

7 5
100
400
300
100
500
101
400

예제 출력 1 복사

500

코드

/*
    용돈관리
    이분탐색, 문제이해력
*/
/*
    용돈관리
    이분탐색, 문제이해력
*/
import java.io.*;
import java.util.*;
public class p6236 {
    static int totalDayCnt, totalWithdrawCnt;
    static int HighestPrice;
    static int[] costArr;
    static int sum;
    public static void main(String[] args) throws IOException {
        initValue();
        minWithdrawPrice();
    }

    static void initValue() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        totalDayCnt = Integer.parseInt(st.nextToken());
        totalWithdrawCnt = Integer.parseInt(st.nextToken());
        costArr = new int[totalDayCnt];
        for (int i = 0; i < totalDayCnt; i++) {
            costArr[i] = Integer.parseInt(br.readLine());
            HighestPrice = Math.max(HighestPrice, costArr[i]);
            sum += costArr[i];
        }
    }

    // 이분탐색 실행 함수
    static void minWithdrawPrice() {
        int answer = 0;

        // 최소 금액: 1 (원)
        // 최대 금액: 가장 높은 금액 x 총 일수 (원)
        int lo = 1;
        int hi = HighestPrice * totalDayCnt;
        answer = hi;
        while (lo <= hi) {
            int testPrice = (lo + hi) / 2;
            // testPrice 금액을 추출하면서 모든 조건을 만족하며 totalDayCnt동안 버틸 수 있는 가?
            // 버틸 수 있다면 금액을 점차적으로 줄여보면서 테스트한다.
            if (isPossible(testPrice)) {
                hi = testPrice - 1;
                answer = Math.min(answer, testPrice);
            } else { // 버틸 수 없다면 금액을 점차적으로 늘려보면서 테스트한다.
                lo = testPrice + 1;
            }
        }
        System.out.println(answer);
    }

    static boolean isPossible(int mid) {
        // 남아있는 돈의 초기값은 처음 가지고 있던 돈.
        int remain = mid;
        int cnt = 1;

        for (int i = 0; i < totalDayCnt; i++) {
            // 해당 금액으로 하루라도 만족하지 못하면 false
            if (mid < costArr[i]) return false;

            if (remain - costArr[i] < 0) {
                remain = mid;
                cnt++;
            }
            remain -= costArr[i];
        }

        return cnt <= totalWithdrawCnt;
    }
}