백준 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