6236번: 용돈 관리

문제

현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 합니다. 인출할 때는 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 쓰고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출합니다. 이때 현우가 인출해야 할 최소 금액 K를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 N(1 ≤ N ≤ 100,000)과 M(1 ≤ M ≤ N)이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 각 날에 이용할 금액이 주어집니다. (금액은 1 이상 10,000 이하)
• 출력: 첫째 줄에 현우가 인출해야 할 최소 금액 K를 출력합니다.

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

풀이: 매개변수 탐색(Parametric Search)을 활용한 최소 인출 금액 찾기

현우가 1회 인출하는 금액 K(코드의 mid)를 이분 탐색을 통해 찾아내는 매개변수 탐색 풀이입니다. 가능한 금액의 최댓값이 최대 10억이므로 이분 탐색으로 접근해야 합니다.

• 이분 탐색 범위 설정: 인출 금액의 최솟값 s = 1로, 최댓값 e는 모든 금액의 합이 될 수 있는 최대치인 1,000,000,000으로 설정합니다.
• 조건 판별 (check 함수): 중간값 mid를 1회 인출 금액(K)으로 가정하고 N일을 보낼 수 있는지, 그리고 인출 횟수가 M번 이하인지 확인합니다.
  1. 각 날의 소비 금액 a[i]를 순회합니다.
  2. 현재 가진 돈(sum)이 a[i]보다 부족하다면, 남은 돈을 집어넣고 다시 mid만큼 인출합니다. (sum = mid; cnt++;)
  3. 인출을 했는데도 현재 쓸 금액보다 작다면(sum < a[i]), 이 인출 금액(mid)으로는 하루를 보낼 수 없다는 뜻이므로 즉시 false를 반환합니다.
  4. 정상적으로 지출이 가능하다면 남은 돈에서 차감합니다. (sum -= a[i];)
  5. 최종 인출 횟수 cnt가 목표 횟수 m 이하인지 반환합니다. (횟수가 남는다면 남은 금액을 넣었다 빼는 방식으로 M번을 무조건 맞출 수 있으므로 cnt <= m이면 조건 만족입니다.)
• 최소 금액 탐색: check(mid)가 참이라면 인출 금액을 더 줄일 수 있는지 확인하기 위해 상한선을 내리고(e = mid - 1), 정답 후보 ans를 갱신합니다. 거짓이라면 금액이 부족한 것이므로 하한선을 올립니다(s = mid + 1).

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[] a;

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

       StringTokenizer st = new StringTokenizer(br.readLine());
       n = Integer.parseInt(st.nextToken());
       m = Integer.parseInt(st.nextToken());

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

       int s = 1;
       int e = 1000000000;
       int ans = 0;
       while (s <= e) {
          int mid = (s + e) / 2;

          if (check(mid)) {
             e = mid - 1;
             ans = mid; // 조건을 만족하는 최소 K값 갱신
          } else {
             s = mid + 1;
          }
       }

       bw.write(ans + "");

       bw.flush();
    }

    static boolean check(int mid) {
       int sum = 0;
       int cnt = 0;
       for (int i = 0; i < n; i++) {
          // 현재 가진 돈이 부족하면 다시 인출
          if (sum < a[i]) {
             sum = mid;
             cnt++;
          }
          // 인출한 금액으로도 쓸 돈을 충당 못하면 불가능한 금액
          if (sum < a[i])
             return false;
          
          sum -= a[i];
       }

       // 인출 횟수가 M번 이하인지 확인
       return cnt <= m;
    }
}

알고리즘 분류

이분 탐색 (Binary Search), 매개변수 탐색 (Parametric Search)