[Algo] 백준 23843 콘센트 JAVA

코드

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

public class Main {
    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 M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < M; i++) {
            pq.add(0);
        }
        for (int i = N - 1; i >= 0; i--) {
            int tmp = pq.poll() + arr[i];
            pq.add(tmp);
        }
        int ans = 0;
        while (!pq.isEmpty()) {
            ans = Math.max(pq.poll(), ans);
        }
        System.out.println(ans);
    }
}

 

풀이

콘센트가 M개 일 때, 최소시간으로 N개의 기기를 충전하도록 하는 문제이다. 노는 콘센트가 최소여야하고 빨리 일을 끝낸 콘센트는 얼른 다른 기기를 충전시켜야 한다. 그렇다면 이미 일을 다 끝낸 충전기를 찾아야 한다.

기기를 정렬해 가장 시간이 오래걸리는 것부터 실행하고, 콘센트 우선순위 큐를 만들어 충전이 끝난 것(=작은 수) 을 반환받아 다음 충전을 더해주면 된다.