2022.03.07 72일차

백준 6236번 (용돈 관리)

문제

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

나의 풀이

1. N일 동안 금액, M번만 통장에서 인출, K원 인출
2. 최소 금액 => 이분 탐색으로 접근, 금액을 기준
3. 최소값: 1, 최대값: 1000000000(N의 최대값 * 금액의 최대값)
4. 조건1. K(mid)는 금액보다 커야 한다. (하루에 인출 한 번)
   • mid < use이면 조건 불충족 넘어가기, min 변경
5. 조건2. 인출횟수(count)는 M번보다 크면 안된다. (작아도 상관x)
   • money 변수 사용
   • money가 금액보다 크거나 같으면 금액 빼기
   • money가 금액보다 작으면 money를 mid - 금액으로 변경, count 증가
6. count > M이거나 mid < use이면 min 변경
7. 나머지 경우 max 변경

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());

        long min = 1;
        long max = 1000000000;
        long answer = Integer.MAX_VALUE;

        int[] useMoney = new int[N];

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

        while (min <= max) {
            long mid = (min + max) / 2;
            long money = 0;
            int count = 0;
            boolean con1 = false;

            for (int use : useMoney) {
                if (mid < use) {
                    con1 = true;
                    break;
                }

                if (money >= use) {
                    money -= use;
                } else {
                    count++;
                    money = mid - use;
                }

                if (count > M) break;
            }

            if (count > M || con1){
                min = mid + 1;
            } else {
                 answer = mid;
                 max = mid - 1;
            }

        }

        System.out.println(answer);
    }
}

생각하기