[백준] 3079번 - 입국심사 (Gold 5)

문제 링크

백준 3079번 - 입국심사 (Gold 5)

문제 설명

문제는 길게 쓰여져있지만 수식으로 요약하면 간단하다.
$\sum_{i=1}^{N}{a_i} = M$(단, $a_i$는 모두 0 이상의 정수)일 때 $\mathrm{max}\lbrace{a_i T_i : i = 1, \cdots N}\rbrace$의 최솟값을 구하는 문제이다.

정답 코드 및 설명

T초 이내로 심사를 마칠 수 있는 사람의 수는 최대 $\sum_{i=1}^{N}{(T / T_i)}$이다.
$T_i$ 중 가장 작은 값이 t라면, Mt초 이내에는 반드시 심사를 끝낼 수 있다.
위 두 사실을 이용하여 매개변수탐색을 사용한다.

아래 코드에서는 t를 구하기 위해 정렬을 사용했는데, 이는 불필요하고 최솟값만 구하면 된다.

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

public class BOJ3079 {
    int n, m;
    int[] t;

    void input() 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());
        t = new int[n];
        for (int i = 0; i < n; i++)
            t[i] = Integer.parseInt(br.readLine());
        Arrays.sort(t);
    }

    long minTime() {
        long start = m * (long) t[0];
        long end = 0;
        while (start > end + 1) {
            long mid = (start + end) / 2;
            if (maxPeople(mid) >= m) start = mid;
            else end = mid;
        }
        return start;
    }

    long maxPeople(long mid) {
        long people = 0;
        for (int i = 0; i < n; i++)
            people += mid / t[i];
        return people;
    }

    void solution() throws IOException {
        input();
        System.out.println(minTime());
    }

    public static void main(String[] args) throws IOException {
        new BOJ3079().solution();
    }
}