[백준]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 ≤ 금액 ≤ 10000)

출력

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

예제 입력 1

7 5
100
400
300
100
500
101
400

예제 출력 1

500

풀이

지문 이해가 중요한 문제이다. 최종적으로 구해야 하는 것은 M번만큼만 인출을 해서 N일을 지낼 수 있는 최소금액을 구하는 문제이다.

해당 문제는 이분탐색을 통해 풀어나갈 수 있다. 이유는 정해진 범위에서 특정값을 찾는 구조로 풀어나가야지 최소값을 찾을 수 있기 때문이다.

문제를 살펴보면 첫날은 무조건 K금액을 인출을 해야하기 때문에 1회부터 시작을 한다. 여기서 케이스가 갈라진다.

만약 i번째 쓴 돈이 남거나 부족하지 않으면 다음날까지 그냥 그대로 사용하면 된다. 하지만 부족한 경우에는 남은 금액을 다시 넣고 K금액을 다시 인출해야 한다. 이때 우리는 count 값을 올려주면서 최종적으로 M과 count 값을 비교해서 금액을 조정해 나가면 된다.

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[] arr = new int[N];
    int min = Integer.MIN_VALUE;
    int max = 0;
    //#1
    for (int i = 0; i < N; i++) {
        st = new StringTokenizer(br.readLine());
        arr[i] = Integer.parseInt(st.nextToken());
        max += arr[i];
        min = Math.max(min, arr[i]);
    }

    int mid = 0;

    //#2
    while (min <= max) {
        //#3
        mid = (min + max) / 2;
        int count = 1;
        int money = mid;
        //#4
        for (int i = 0; i < N; i++) {
            if (arr[i] > money) {
                money = mid;
                count++;
            }
            money -= arr[i];
            if (money < 0) {
                break;
            }
        }
        //#5
        if (count > M || money < 0) {
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }

    System.out.println(min);
}

해당 문제의 테스트케이스 말고 아래 테스트 케이스로 돌려보면 좀 더 쉽다

3 3
1
1
500

1. 범위를 정하기 위해서 min과 max 값을 선언해주고 입력을 받으면서 각 값을 지정해준다. 이때 min값은 입력받은 범위중에 최대값이 될것이고 max 값은 모든 값들은 더한 값들이 된다
2. 위의 테케로 보면 최소값은 500 최대값은 502가 된다.
3. min값이 max값보다 크거나 같은 경우 반복문의 종료조건을 걸어준다.
4. 최초 처음에는 K금액을 인출 해야하기 때문에 count는 1부터 시작을 하고 money를 mid 값 즉 K 금액으로 설정해준다.
5. i 번째 요일에 얼만큼 썼는지와 부족한지를 판단해 나가면서 count 값을 구한다. 금액이 부족하지 않다면 그냥 해당 날짜에 쓴 금액을 빼고 넘어가고 반대라면 인출횟수(count)를 올려주고 money를 mid로 초기화 해준다. 이때 만약에 금액이 부족해서 money를 mid값으로 초기화 해준 후에도 해당 요일을 넘길 수 없다면 해당 mid 값으로는 M을 절대 만족할 수 없기 때문에 break를 걸고 빠져나온다.
6. 이후에 count값이 M보다 크다면 금액을 더 올려줘야 하기 때문에 min값을 mid + 1로 올려주고 그 반대라면 max값을 줄여준다.