백준 - 용돈 관리(6236)

오늘 풀어볼 문제는 ⭐용돈관리 이다.

1. 문제요약

N일 동안 사용할 금액이 주어질 때, 매번 같은 금액 K만 인출해서 생활한다.
돈이 부족하면 다시 K원을 인출하며, 필요하면 일부러 인출 횟수를 늘려 정확히 M번도 맞출 수 있다.

따라서 구해야 하는 값은
최소 필요 인출 횟수가 M 이하가 되는 최소 K 이다.

2. 알고리즘

이 문제는 K를 기준으로 하는 이분탐색 문제다.

2.1 핵심상태

• 탐색값: 인출 금액 K
• 판별: K로 생활할 때 최소 인출 횟수가 M 이하인가

2.2 핵심과정

• lo는 하루 사용 금액의 최댓값
• hi는 전체 사용 금액의 합
• mid를 K 후보로 두고 인출 횟수를 계산
• 횟수가 M 이하이면 더 작은 K 탐색
• 횟수가 M 초과이면 K를 더 키움

2.3 핵심 규칙

• K는 하루 사용 금액보다 작을 수 없다
• K가 커질수록 인출 횟수는 줄어든다
• 최소 필요 인출 횟수 <= M 이면 가능한 K다
• 따라서 가능한 최소 K 를 찾으면 된다

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, REMAIN;
    static int [] MONEY;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        MONEY = new int[N];

        int lo=0;
        int hi=0;
        for(int i = 0; i < N; i++){
            MONEY[i] = Integer.parseInt(br.readLine());
            hi += MONEY[i];
            lo = Math.max(lo, MONEY[i]);
        }

        REMAIN = 10000;
        System.out.println(binarySearch(lo, hi));
    }

    static int binarySearch(int lo, int hi) {

        int mid;
        while (lo < hi) {
            mid = (lo + hi) / 2;
            if (canTakeOut(mid)) hi = mid; 
            else lo = mid + 1;
        }
        return lo;
    }

    static boolean canTakeOut(int standard) {
        int takeOutCnt = 1;
        int remain = standard;
        for(int money : MONEY) {
            if(money > standard) return false;
            if(money > remain) {
                takeOutCnt ++;
                remain = standard - money;
            }
            else {
                remain -= money;
            }
        }

        return takeOutCnt <= M;
    }
}