백준 19638 센티와 마법의 뿅망치 자바(java)

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

19638번: 센티와 마법의 뿅망치

 

풀이 방법

우선순위 큐를 사용하였다.

• 키가 큰 것을 우선으로 하는 최대힙 우선순위 큐를 생성한다.
• N의 거인들의 키를 모두 큐에 삽입한다.
  • 즉, 큐에서 peek한 요소는 키가 가장 큰 거인의 키가 된다.
• time = 0 부터 최대 T가 될 때까지 큐에서 하나씩 꺼내면서 뿅망치 때리기를 반복한다.
  • 큐에서 peek 한 키가 H보다 작거나 1이라면 바로 반복문을 탈출한다.
  • 그게 아니라면 poll 하여 키를 꺼내고 2로 나눈 키를 다시 큐에 삽입한다.
  • time을 증가시키고 다시 뿅망치 작업을 한다.
• 반복문이 끝난 뒤 큐에서 peek 한 요소가 H보다 작다면 "YES"와 함께 time 값을 출력한다.
• H보다 같거나 작다면 "NO"와 함께 peek한 요소를 출력한다.

 

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int H = Integer.parseInt(line[1]);
        int T = Integer.parseInt(line[2]);
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for(int i=0; i<N; i++) {
            int height = Integer.parseInt(br.readLine());
            pq.add(height);
        }

        int time = 0;
        while(time < T) {
            int height = pq.peek();
            if(height < H || height == 1) {
                break;
            }
            pq.add(pq.poll() / 2); // 뿅망치로 맞은 후 키 삽입
            time++;
        }

        if(pq.peek() < H) {
            System.out.println("YES");
            System.out.println(time);
        } else {
            System.out.println("NO");
            System.out.println(pq.peek());
        }
    }
}