백준 공정 컨설턴트 호석(22254)

공정 컨설턴트 호석

1. 힌트

1) 만약 공정의 라인의 개수 $k$가 정해지면, 선물을 배정하는 것은 공정의 규칙에 따르기만 하면 됩니다. 예제 입력 1 아래에 있는 그림에서 알 수 있듯이, $i$번째 선물은 언제나 지금 사용시간이 가장 적은 라인에 배정하면 됩니다.

2) 공정 라인 개수의 범위는 $1$개부터 최대 $N$개까지 될 수 있습니다. 그 이상 늘어나봐야 의미가 없습니다.

3) $k$개의 공정 라인으로 $X$시간 내에 제작하는데 성공했다면 당연히 $k + 1$개의 공정 라인으로도 시간 내에 제작하는 것이 가능합니다. 이러한 특성을 이용해서 공정 라인 개수의 범위 $[1, N]$에 대해 이분 탐색이 가능합니다.

2. 접근

1) 공정의 규칙

만약 $k$개의 공정 라인의 개수가 주어진다면, $X$시간 안에 만드는 것이 가능할 지는 공정의 규칙에 따라 직접 해보면 알 수 있습니다. 어떻게 이를 구현할 수 있을까요?

$i$번재 선물은 $i-1$번째 선물이 배정된 이후에 사용 시간이 가장 적은 공정 라인 중 하나에 배정된다했으므로 우선순위 큐에 $k$개의 원소를 넣고 그 원소들을 공정 라인 각각의 사용시간의 합이라고 정의합시다. 가장 작은 값을 꺼낸 후에 $i$번째 선물이 필요한 공정 시간을 더해서 다시 넣는 식으로 구현하면 $NlgK$시간에 구현할 수 있습니다.

2) 이분 탐색

공정 라인의 개수의 범위는 어떻게 될까요? 문제에서 주어져있지는 않지만, $[1, N]$범위라는 것을 알 수 있습니다. 만약 공정 라인의 개수가 $N$개라면 시작하자마자 $N$개의 공정 라인에서 동시에 $N$개의 선물을 제작할테니까요.

그런데 우리는 최소 공정 라인의 개수를 구해야합니다. 무식하게 $[1, N]$개의 공정 라인 개수에 대해서 직접 해보면 시간 복잡도는 $O(N^2lgK)$가 되므로 불가능합니다.

여기서 문제의 특성을 이용할 수 있습니다. 바로 $k$개의 공정 라인으로 $X$시간 내에 제작하는데 성공했다면 당연히 $k + 1$개의 공정 라인으로도 시간 내에 제작하는 것이 가능하다는 것입니다. 이러한 성질은 이분 탐색을 할 수 있게 하는 중요한 성질입니다. 이분 탐색을 사용하면 $O(lgN \times NlgK)$시간에 찾는 것이 가능합니다.

3. 구현

public class Main {
    static int N;
    static int[] S;
    
    // k개의 공정으로 t시간 안에 제작할 수 있는지 여부
    static boolean f(int k, int t) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < k; i++) pq.offer(0);
        for (int x : S) {
            int y = pq.poll() + x;
            if (y > t) return false;
            pq.offer(y);
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        S = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
        int lo = 0; int hi = N;
        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (f(mid, X)) hi = mid;
            else lo = mid;
        }
        System.out.println(hi);
    }

}

1) 시간 복잡도

$O(lgN \times NlgK)$