백준 6236 - 용돈 관리(자바 - 이분탐색)

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

6236번: 용돈 관리

 

* 문제 요약

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다.

현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다.

다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액K 를 최소화 하기로 하였다.

현우가 필요한 최소 금액K 를 계산하는 프로그램을 작성하시오.

 

* 입력

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

2번째 줄부터 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 <= 금액 <= 10,000)

 

* 출력

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

 

* 예시

 

* 해결 과정

통장에서 인출할 수 있는 최소 금액은 1이고, 최대 금액은 10,000 * 100,000 이다.

왜냐하면 N의 경우 최대로 들어올 수 있는 입력이 100,000 이고 각 날짜마다 써야하는 돈의 최댓값이 10,000 이기 때문에 최악의 경우 10,000 만큼의 금액을 100,000일 만큼 계속해서 인출해야 할 수도 있기 때문이다.

다음과 같이 이분탐색을 수행해준다.

1. start 를 1, end 를 10,000 * 100,000 으로 초기화해준다.

2. start <= end 조건을 만족하는 동안 다음과 같이 반복을 진행해준다.

  - mid 를 (start + end) / 2 로 초기화해준다. 여기서 mid 는 인출할 금액 K를 뜻한다.

  - 각 날짜별로 필요한 금액을 이중 반복문을 통해 탐색하여, 현재 가지고 있는 금액(current) 이 당일 필요한 금액보다 작다면 현재 가지고 있는 금액을 다시 통장에 넣어준 후(current 를 0으로 초기화) 다음과 같이 조건문을 처리해준다.

    - 만약 mid 값이 당일 필요한 금액보다 크거나 같다면 인출 횟수(count) 를 1 늘려주고 현재 가지고있는 금액(current) 에 mid 만큼을 더해준 다음, 현재 가지고 있는 금액에서 당일 필요한 만큼의 돈을 빼준다.

    - 만약 mid 값이 당일 필요한 금액보다 작다면 인출할 때 더 큰 돈이 필요하단 뜻이므로 더 이상 로직을 수행해주지 않고 반복문을 종료해준다.

    - 이중 반복문이 종료된 이후 인출할 때 더 많은 돈이 필요하거나, 인출 횟수(count) 가 M보다 크다면 start 를 mid + 1 로 초기화하여 mid 값이 더 커지는 방향으로 범위를 줄여준다.

    - 반대로 인출 횟수(count) 가 M보다 작거나 같다면 현재 mid 값을 정답 변수 result 에 저장해주고 난 다음, end 를 mid - 1 로 초기화하여 mid 가 더 작아지는 방향으로 범위를 줄여준다.

  - 반복문이 끝나고 나면 result 를 출력시켜 준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;

public class Main {

    static int N = 0;
    static int M = 0;
    static int[] dayArray = null;

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

        String[] inputArray = br.readLine().split(" ");

        N = Integer.parseInt(inputArray[0]);
        M = Integer.parseInt(inputArray[1]);

        dayArray = new int[N];
        for (int i = 0; i < dayArray.length; i++) {
            dayArray[i] = Integer.parseInt(br.readLine());
        }

        int start = 1;
        int end = 10000 * 100000;

        int result = 0;
        while (start <= end) {

            int mid = (start + end) / 2;
            if (check(mid)) {
                result = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean check(int mid) {

        boolean result = true;
        int current = 0;
        int count = 0;
        for (int i = 0; i < dayArray.length; i++) {
            int dayRequire = dayArray[i];

            if (current < dayRequire) {
                current = 0;

                if (mid >= dayRequire) {
                    count++;
                    current += mid;
                } else {
                    result = false;
                    break;
                }
            }

            current -= dayRequire;
        }

        if (count > M) {
            result = false;
        }

        return result;
    }
}

 

전체  날짜를 기준으로 인출할 때 총 필요한 최소 금액 1, (N = 1, 모든 N회의 입력에 대해 필요한 금액이 1인 경우) 인출할 때 총 필요한 최대 금액 10,000 * 100,000 (N = 100,000, 모든 N회의 입력에 대해 필요한 금액이 10,000 인 경우)을 최초 범위로 설정하고, 실제로 인출할 때 중간값만큼을 인출한다고 할 때 필요한 인출 횟수가 M보다 큰 경우, 작거나 같은 경우에 따라 범위를 줄여가며 인출할 때 필요한 최소한의 금액을 찾았으므로 매개변수 탐색 문제에 해당된다.