14627번: 파닭파닭

문제

승환이는 S개의 파를 사와서 C개의 파닭에 파채를 올리려고 합니다. 각각의 파닭에는 동일한 길이의 파채가 들어가야 하며, 최대한 많은 양의 파를 넣고자 합니다. 파닭에 사용하고 남은 자투리 파들은 모아서 라면에 넣을 예정입니다. 라면에 들어갈 파의 총 길이를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 파의 개수 S (1 ≤ S ≤ 1,000,000)와 파닭의 수 C (1 ≤ C ≤ 1,000,000)가 주어집니다. 둘째 줄부터 S개의 줄에 파의 길이(1 ≤ 길이 ≤ 1,000,000,000)가 주어집니다.
• 출력: 첫째 줄에 라면에 넣을 파의 총 길이를 출력합니다.

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

풀이: 매개변수 탐색(Parametric Search)을 활용한 길이 최적화

가장 긴 파채의 길이(len)를 이분 탐색을 통해 찾아내는 매개변수 탐색 풀이입니다. 파의 개수와 길이가 매우 크기 때문에 순차 탐색 대신 이분 탐색을 사용해야 시간 초과를 피할 수 있습니다.

• 이분 탐색 범위 설정: 파채 길이의 최솟값 l = 1로, 최댓값 r은 입력받은 파 중 가장 긴 파의 길이로 설정합니다.
• 조건 판별 (check 함수): 중간값 m으로 각 파를 잘랐을 때 나오는 파채의 총 개수(cnt)를 계산합니다. 이 개수가 목표치 c 이상이라면, 해당 길이로 파닭을 만들 수 있다는 뜻입니다.
• 최대 길이 탐색: check(m)이 참이라면 더 길게 자를 수 있는지 확인하기 위해 하한선을 올리고(l = m + 1), 정답 후보 len을 갱신합니다. 거짓이라면 길이를 줄여야 하므로 상한선을 내립니다(r = m - 1).
• 나머지 계산 및 오버플로우 주의: (전체 파 길이의 합) - (파닭 수 C * 파채 최대 길이 len) 로 남은 파의 길이를 구합니다. 또한, 전체 파 길이의 합은 int형의 최댓값을 초과할 수 있으므로 반드시 long 타입을 사용해야 안전합니다.

코드

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

public class Main {
    static int s, c;
    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());
       s = Integer.parseInt(st.nextToken());
       c = Integer.parseInt(st.nextToken());

       a = new int[s];
       int r = 0;
       long sum = 0; // 총 파의 길이를 저장하기 위해 long 사용
       for (int i = 0; i < s; i++) {
          a[i] = Integer.parseInt(br.readLine());
          r = Math.max(r, a[i]);
          sum += a[i]; // 파 길이의 총합 누적
       }

       int l = 1;
       int len = 1;
       while (l <= r) {
          int m = (l + r) / 2;
          if (check(m)) {
             l = m + 1;
             len = m; // 가능한 최대 파채 길이 갱신
          } else {
             r = m - 1;
          }
       }

       // 전체 파의 길이에서 파닭에 들어간 파의 길이(C * len)를 뺌
       long ans = sum - (long) c * len;

       bw.write(ans + "");

       bw.flush();
    }

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

       return cnt >= c;
    }
}

알고리즘 분류

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