백준 23843번 콘센트 Java

: ) YOUNG·2024년 5월 14일
1

알고리즘

목록 보기
370/417
post-thumbnail

백준 23843번
https://www.acmicpc.net/problem/23843

문제



생각하기


  • 그리디, 우선순위 큐


동작

전자기기 N개를 콘센트 M개로 가장 짧은 시간에 모두 완충하는 시간을 구해야한다.

가장 긴 충전 시간을 가지는 순서대로 멀티 방식으로 충전하면 된다.


        PriorityQueue<Integer> pque = new PriorityQueue<>();
        int idx = N - 1;
        while (idx >= 0) {

            if (pque.size() < M) {
                pque.offer(machines[idx]);
                idx--;
                continue;
            }

            int temp = pque.poll() + machines[idx];
            pque.offer(temp);
            idx--;
        }

pque에 긴 시간의 순서대로 먼저 넣고 idx가 0이 될 때까지 먼저 끝나는 기기의 시간 + 다음 기기의 필요 충전 시간을 더하면
각 작업이 끝나고 진행된 시간을 구할 수 있다.

그리고 마지막에 idx가 0이 되고 남은 작업을 pque에서 모두 마무리 지으면 최종적으로 끝나는 시간이 정답이 된다.



결과


코드



import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[] machines;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> pque = new PriorityQueue<>();
        int idx = N - 1;
        while (idx >= 0) {

            if (pque.size() < M) {
                pque.offer(machines[idx]);
                idx--;
                continue;
            }

            int temp = pque.poll() + machines[idx];
            pque.offer(temp);
            idx--;
        }

        int ans = 0;
        while (!pque.isEmpty()) {
            ans = pque.poll();
        }

        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        machines = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            machines[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(machines);
    } // End of input()
} // End of Main class

0개의 댓글