[BOJ22254] 공정 컨설턴트 호석(이진탐색, 매개변수 탐색, 우선순위 큐)

 

 

---

문제 링크

https://www.acmicpc.net/problem/22254

22254번: 공정 컨설턴트 호석

 

문제 풀이

- "모든 선물을 X 시간 내에 만들 기 위한,  공정 라인의 최소값" 으로 문제 해석하여 매개변수 탐색으로 풀이

- PriorityQueue 사용하여 공정 라인 수가 정해졌을 때 X 시간내 선물 생산 가능 여부 확인 (boolean)

- 선물 개수 N =최대 10^5개, 제작 완료 X = 10^9 시간 제한 걸리고, 각 선물의 공정시간이 10^9일 때 공정라인은 10^5 (=N)개가 있어야 생산가능하다. ( int 범위 )

 

절차

1) 매개변수(이진) 탐색으로 mid( 공정 라인 수) 정함

- 해당 공정 라인으로 X 시간내 생산 가능한 경우 답을 갱신하고 R = mid - 1 줄인다(생산 라인을 줄인다, 최소값 찾기)

- 생산 불가인 경우 L = mid + 1 (생산라인 늘린다.)

2) X 시간내에 생산 가능 여부는 

- 우선 순위 큐 정의 (내림차순 정렬) 

- 선물 주문 개수 N개 만큼, 각 선물의 공정 시간을 순차 조회하면서 우선 순위 큐에 공정 라인 시간을 갱신 

- 이때 공정 라인의 시간이 X 초과하는 경우 생산 불가하므로 false 리턴 ( 공장 라인을 증가 시켜라!! L = mid + 1)

 

제출 코드

참고. 굳이 우선 순위 큐에 담을 객체 선언할 필요없이 공정 라인 개수만큼 0을 넣어 초기화하여 풀이 가능

Queue<Integer> que = new PriorityQueue<>(); // 기본 오름차순 
for(int i = 1; i <= 공정라인수; i++) que.add(0);

위의 방식이 좀 더 메모리 덜 잡아 먹는다. 

 

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

public class Main {
    
    static int N;
    static long X;
    static long[] time;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        X = Long.parseLong(st.nextToken());

        time = new long[N + 1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            time[i] = Long.parseLong(st.nextToken());
        }
    }

    static class Line implements Comparable<Line> {
        int idx;
        long time;

        public Line(int idx, long time) {
            this.idx = idx;
            this.time = time;
        }

        @Override
        public int compareTo(Line o) { // 오름차순
            if(time < o.time) return -1;
            else if(time == o.time) return 0;
            return 1;
        }
    }

    static boolean possible(int lines, long limit) {
        Queue<Line> que = new PriorityQueue<>();
        for(int i = 1; i <= lines; i++) {
            que.add(new Line(i, time[i]));
        }

        int idx = lines + 1;
        while(idx <= N) {
            Line cur = que.poll();

            if(cur.time + time[idx] > limit) return false;

            cur.time += time[idx];
            que.add(cur);
            idx += 1;
        }

        return true;
    }

    static void pro() {
        int L = 1;
        int R = N;
        int ans = 0;

        while(L <= R) {
            int mid = (L + R) / 2;

            if(possible(mid, X)) {
                ans = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}