[백준] 19638번. 센티와 마법의 뿅망치(JAVA)

문제

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

---

풀이(8분)

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));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순
        for(int i = 0; i < N; i++){
            pq.add(Integer.parseInt(br.readLine()));
        }

        int cnt = 0;
        while(T-- > 0){ // 뿅망치 횟수
            int cur = pq.poll();
            if(cur < H){ // 최댓값이 H보다 작다면
                System.out.println("YES"); // 바로 정답 출력
                System.out.println(cnt);
                return;
            }
            if(cur == 1){
                pq.add(1);
                continue;
            }
            cnt++;
            pq.add((int)Math.floor(cur/2)); // 2로 나눈 뒤 버림
        }

        // 만약 끝난 상태에서 최댓값이 H보다 작다면
        if(pq.peek() < H){
            System.out.println("YES");
            System.out.println(cnt);
            return;
        }

        // 불가능하다면
        System.out.println("NO");
        System.out.println(pq.poll());
    }
}

---

문제 풀이 전략

 

N의 범위가 10^5이고, 작업 횟수가 10^5이기 때문에 O(HlogN)을 해도 문제없을 것이라고 판단하여 우선순위 큐를 도입했다.

우선순위큐는 내부적으로 이진힙을 사용하여 O(logN)으로 정렬을 할 수 있기 때문이다.

 

1. 반복 (최대 T번: 뿅망치 사용)
   • 가장 큰 키(cur)를 꺼냄
   • (조건 1) cur < H → 모두 조건 충족 → "YES" 출력 후 종료
   • (조건 2) cur == 1 → 줄일 수 없으니 다시 넣고 다음 턴
   • (그 외) → 뿅망치 사용 횟수 cnt++, cur/2를 큐에 삽입
2. 반복 종료 후 확인
   • 큐의 최댓값이 여전히 H보다 작으면 "YES", 사용 횟수 출력
   • 아니면 "NO", 가장 큰 값 출력