[백준 - 23843][GOLD 5][해설 X] - 콘센트 (JAVA)

문제 링크

---

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

 

문제

---

광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다.

전자기기들은 한 번에 하나의 콘센트에서만 충전이 가능하고, 충전에 필요한 시간은 2k(0 ≤ k ≤ 15, k는 정수) 형태이다.

광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간이 얼마인지 알려주자.

 

입력

---

첫째 줄에 전자기기의 개수 N과 콘센트의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10)

둘째 줄에 충전에 필요한 시간 ti를 나타내는 N개의 정수가 주어진다. (20 ​≤ ti ≤ 215, ti = 2k (0 ≤ k ≤ 15, k는 정수))

 

출력

---

 

충전에 필요한 최소 시간을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
/*
*
* 빨리 끝낸다 -> 최대한 많이 동시에 실행한다. -> 가장 느린것부터 시작하면서 먼저 끝난것에 그다음 느린것을 시작한다.
*
* */
public class Main {
    public static void main(String[] args) throws Exception{
        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());

        int[] chargeTime = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(chargeTime);

        int currentTime = 0;

        PriorityQueue<Integer> flug = new PriorityQueue<>();

        //가장 충전시간이 긴 것부터 실행
        for(int i=chargeTime.length-1;i>=0;i--){
            //더이상 꽇을 플러그가 없다면 가장 먼저 끝나는 플러그를 뽑는다.
            while(flug.size()==M){
                currentTime = flug.poll();
            }
            //플러그에 꽂기
            flug.add(currentTime + chargeTime[i]);
        }

        //나머지 충전시간 중 가장 긴 시간을 저장
        while(!flug.isEmpty()){
            currentTime = flug.poll();
        }

        System.out.println(currentTime);
    }
}

 

 

실행 결과

---

 

팁

---

• 최대 값 문제는 DP, 그리디, 완전탐색 중에서 생각해보자.
• 가장 짧게 빈틈없이 구간을 만드려면 가장 긴 것 부터 넣어야 한다.