2792번: 보석 상자

문제

보석 상자에 M가지 서로 다른 색상의 보석이 있습니다. 이 보석들을 N명의 학생들에게 나누어 주려고 합니다. 학생들은 받지 못할 수도 있지만, 보석을 받는다면 항상 같은 색상의 보석만 가져가야 합니다. 이때, 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수(질투심)를 최소화하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 학생의 수 N(1 ≤ N ≤ 1,000,000,000)과 색상의 수 M(1 ≤ M ≤ 300,000)이 주어집니다. 둘째 줄부터 M개의 줄에 걸쳐 각 색상 보석의 개수가 주어집니다. (보석의 개수는 1 이상 1,000,000,000 이하)
• 출력: 첫째 줄에 질투심의 최솟값을 출력합니다.

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

풀이: 매개변수 탐색(Parametric Search)을 활용한 질투심 최소화

가장 많은 보석을 가져가는 학생의 보석 수(질투심)인 mid를 이분 탐색을 통해 찾아내는 매개변수 탐색 풀이입니다. N의 범위가 최대 10억이므로 완전 탐색이 아닌 이분 탐색으로 접근해야 합니다.

• 이분 탐색 범위 설정: 한 명의 학생이 가져갈 수 있는 보석의 최소 개수 s = 1로, 최대 개수 e는 주어진 보석 중 가장 개수가 많은 색상의 보석 수로 설정합니다.
• 조건 판별 (check 함수): 중간값 mid를 질투심(한 학생이 가져가는 최대 보석 수)으로 가정하고, 각 색상의 보석을 나누어 줄 때 필요한 학생 수를 계산합니다.
  1. 각 색상의 보석 개수 a[i]를 순회합니다.
  2. a[i]를 mid로 나눈 몫(a[i] / mid)만큼 학생들에게 나누어 줍니다.
  3. 만약 나누어 주고 남은 보석이 있다면(a[i] % mid != 0), 남은 보석들도 같은 색상이므로 한 명의 학생에게 마저 주어야 합니다. 이는 수학적으로 올림 연산과 동일합니다.
  4. 최종적으로 보석을 나누어 받은 학생 수 cnt가 목표 학생 수 n 이하인지 반환합니다. (학생 수가 n보다 작다면 빈손인 학생이 있어도 된다는 조건에 부합하므로 가능합니다.)
• 최소 질투심 탐색: check(mid)가 참이라면 질투심(최대 보석 수)을 더 줄일 수 있는지 확인하기 위해 상한선을 내리고(e = mid - 1), 정답 후보 ans를 갱신합니다. 거짓이라면 학생 수가 n명을 초과한 것이므로 한 명당 가져가는 보석 수를 늘려야 합니다. 따라서 하한선을 올립니다(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[m];
       int e = 0;
       for (int i = 0; i < m; i++) {
          a[i] = Integer.parseInt(br.readLine());
          e = Math.max(e, a[i]);
       }

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

          if (check(mid)) {
             e = mid - 1;
             ans = mid;
          } else {
             s = mid + 1;
          }
       }
       
       bw.write(ans + "");

       bw.flush();
    }

    static boolean check(int mid) {
       int cnt = 0;
       for (int i = 0; i < m; i++) {
          cnt += (a[i] + mid - 1) / mid;
       }

       return cnt <= n;
    }
}

알고리즘 분류

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