문제

풀이 과정

요약

우선순위 큐를 활용한 문제

상세

1. 가장 적게 충전하는 방법은, 가장 충전시간이 오래 걸리는 거 부터 충전하는 것이다. 이를 위해 우선순위큐를 사용한다.

2. 나의 경우에는 전자기기를 내림차순하기 위한 용도의 $pq1$ 과 콘센트를 오름차순 하기 위한 $pq2$ 를 준비했다. $pq2$ 를 오름차순으로 한 이유는 가장 먼저 0에 도달해는 애들부터 뽑아내기 위해서이다.

3. 시간이 오래걸리는 애들부터 뽑아서 $pq2$ 에 꽂아둔다. 현 시점의 $pq2.peek()$ 이 충전할 제품을 바꿀 때 현재까지 소모한 시간이 된다.

4. 충전이 완료된 애들은 $pq2$ 에서 뽑아내고, 아직 남은 애들은 $q$ 에 옮겨주자.

5. 현재 걸린 시간을 누적하고 $q$ 의 값들을 다시 $pq2$ 에 옮기자.

6. 이 과정을 $pq2$ 가 텅 빌 때까지 계속 반복한다.

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static PriorityQueue<Integer> pq1, pq2;
    static int N,M;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        // 전자기기 개수, 콘센트 개수
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());

        // pq1 : 전자기기 내림차순
        // pq2 : 콘센트 오름차순
        pq1 = new PriorityQueue<>((n1,n2) -> n2-n1);
        pq2 = new PriorityQueue<>((n1,n2)-> n1-n2);
        Queue<Integer> q = new LinkedList<>();

        stk = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) pq1.add(Integer.parseInt(stk.nextToken()));

        charge();

        // 시작!
        int ans = 0;
        while(!pq2.isEmpty()) {
            int t = pq2.peek();

            // 시간만큼 감소
            for(int i=0; i<M; i++) {
                if(pq2.peek()-t == 0) pq2.poll();
                else q.add(pq2.poll()-t);
                if(pq2.isEmpty()) break;
            }

            while(!q.isEmpty()) pq2.add(q.poll());

            ans +=t;

            charge();
        }
        System.out.println(ans);
    }

    private static void charge() {
        while(pq2.size() != M) {
            if(pq1.isEmpty()) break;
            pq2.add(pq1.poll());
        }
    }
}