[백준] 6236. 용돈 관리

문제 링크

[백준] 6236. 용돈 관리

풀이 과정

이분탐색 문제입니다. 코드를 보며 설명하겠습니다.

int low = 1, high = (int) 1e9, answer = 0;

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

먼저 필요한 변수들을 선언해줍니다.

• low 값은 이용 금액의 최대값으로 갱신해줍니다. 그래야지 인출을 몇 번을 하던 간에 주어진 N번의 금액을 사용할 수 있기 때문입니다. 예를 들어, 3일 간 100원, 200원, 300원을 이용한다고 치면, 최소 300원은 뽑아야 모든 날을 커버할 수 있습니다. 300원 미만으로 인출 시, 300원을 쓰는 날엔 하루를 보낼 수 없게 됩니다.
• high 값은 N이 최대로 가능한 100,000의 경우, 각 날짜에 최대 금액 10,000원을 사용한다고 치면, 딱 한 번 $100,000*10,000$원을 인출해 모든 날을 사용할 수 있기 때문에 $10^9$로 설정해주었습니다.

while (low <= high) {
    int mid = (low + high) / 2;

    if (getCnt(mid) > M) {
        low = mid + 1;
    } else {
        answer = mid;
        high = mid - 1;
    }
}

이분 탐색을 진행합니다. mid 값으로 getCnt 메소드 를 호출해, 인출 횟수를 가져옵니다.

• 인출 횟수가 M 을 초과하는 경우, 더 적은 인출 횟수를 만들기 위해 하한선을 조정합니다. low 값을 올려, 더 큰 금액으로 인출하게 되면, 인출 횟수가 줄어들게 됩니다.
• 인출 횟수가 M 이하인 경우, mid 값을 보관해두고, 더 적은 인출 금액을 맞추기 위해 상한선을 조정합니다. high 값을 내려, 더 적은 금액으로 인출했을 때의 인출 횟수를 확인합니다.
• 위 과정이 $low \leq high$ 일 동안 반복합니다. low 가 high 보다 커지기 직전의 answer 가 최종 답이 됩니다.

static int getCnt(int mid) {
    int remain = mid;
    int cnt = 1;

    for (int i = 0; i < N; i++) {
        if (remain - costs[i] < 0) {
            remain = mid;
            cnt++;
        }

        remain -= costs[i];
    }

    return cnt;
}

getCnt 메소드 는 입력받은 mid 값으로 인출 횟수를 구해 리턴합니다.

코드

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

public class Main {
    static int N, M;
    static int[] costs;

    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());
        costs = new int[N];
        int low = 1, high = (int) 1e9, answer = 0;

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

        while (low <= high) {
            int mid = (low + high) / 2;

            if (getCnt(mid) > M) {
                low = mid + 1;
            } else {
                answer = mid;
                high = mid - 1;
            }
        }

        System.out.println(answer);
    }

    static int getCnt(int mid) {
        int remain = mid;
        int cnt = 1;

        for (int i = 0; i < N; i++) {
            if (remain - costs[i] < 0) {
                remain = mid;
                cnt++;
            }

            remain -= costs[i];
        }

        return cnt;
    }
}