[99클럽 4기 코테 스터디 TIL 21일차] 센티와 마법의 뿅망치 (feat. 최대힙)

1) 문제

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

센티는 마법 도구들을 지니고 여행을 떠나는 것이 취미인 악당이다.

거인의 나라에 도착한 센티는 자신보다 키가 크거나 같은 거인들이 있다는 사실이 마음에 들지 않았다.

센티가 꺼내 들은 마법 도구는 바로 마법의 뿅망치로, 이 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 2 ⌋로 변하는 마법 도구이다. 단, 키가 1인 경우 더 줄어들 수가 없어 뿅망치의 영향을 받지 않는다.

하지만 마법의 뿅망치는 횟수 제한이 있다. 그래서 센티는 마법의 뿅망치를 효율적으로 사용하기 위한 전략을 수립했다. 바로 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.

과연 센티가 수립한 전략에 맞게 마법의 뿅망치를 이용한다면 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있을까?

입력

첫 번째 줄에는 센티를 제외한 거인의 나라의 인구수 N (1 ≤ N ≤ 105)과 센티의 키를 나타내는 정수 Hcenti (1 ≤ Hcenti ≤ 2 × 109), 마법의 뿅망치의 횟수 제한 T (1 ≤ T ≤ 105)가 빈칸을 사이에 두고 주어진다. 

두 번째 줄부터 N개의 줄에 각 거인의 키를 나타내는 정수 H (1 ≤ H ≤ 2 × 109)가 주어진다.

출력

마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수를 출력한다.

마법의 뿅망치를 센티의 전략대로 남은 횟수 전부 이용하고도 거인의 나라에서 센티보다 키가 크거나 같은 거인이 있는 경우, 첫 번째 줄에 NO를 출력하고, 두 번째 줄에 마법의 뿅망치 사용 이후 거인의 나라에서 키가 가장 큰 거인의 키를 출력한다.

예제 입력 1 

1 10 1
20

예제 출력 1 

NO
10

예제 입력 2 

2 10 3
16
32

예제 출력 2 

YES
3

예제 입력 3 

2 10 3
127
8

예제 출력 3 

NO
15

예제 입력 4 

1 1 100000
1

예제 출력 4 

NO
1

 

 

 

 

2) 내가 구현한 코드

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer 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 usedHammer = 0; // 사용한 뿅망치 수

        // 뿅망치 사용
        while (T > 0 && !pq.isEmpty()) {
            int tallest = pq.poll(); // 가장 큰 키의 거인

            if (tallest < H) { // 센티의 키가 더 크다면 종료
                bw.write("YES\n");
                bw.write(usedHammer + "\n");
                bw.flush();
                return;
            }

            if (tallest == 1) { // 거인의 키가 1이라면 더 줄일 수 없음
                pq.add(tallest);
                break;
            }

            pq.add(tallest / 2); // 뿅망치를 사용하여 키를 반으로 줄임
            usedHammer++;
            T--;
        }

        // 뿅망치 사용 후에도 센티의 키가 작다면 실패
        int tallest = pq.isEmpty() ? 0 : pq.peek();
        if (tallest < H) {
            bw.write("YES\n");
            bw.write(usedHammer + "\n");
        } else {
            bw.write("NO\n");
            bw.write(tallest + "\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }
}

로직의 흐름은 아래과 같다.

1. 초기화 및 입력
   • PriorityQueue는 최대 힙으로 설정해 가장 큰 거인의 키를 효율적으로 가져옴
   • 거인의 키를 모두 큐에 추가
2. 반복 조건
   • 뿅망치를 사용하기 전, 가장 큰 키가 센티의 키보다 작아지면 종료
   • 뿅망치를 사용할 수 없는 경우(거인의 키가 1이거나 뿅망치 횟수를 모두 사용한 경우)도 처리
3. 출력
   • 센티의 키가 더 커졌다면 사용한 뿅망치 횟수를 출력
   • 모든 뿅망치를 사용했음에도 센티의 키가 가장 큰 거인의 키보다 작다면 실패를 출력

 

3) 추가 구현 코드

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

public class Main {
    static int N,H,T;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        String answer = "NO";
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

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

            // 최장신이 나보다 작거나 1일경우 break;
            if ((pq.peek() < H) || (pq.peek() == 1)) break;
            cnt++;
            pq.add(pq.poll() / 2);
        }
        if (pq.peek() < H) answer = "YES";
        StringBuilder sb = new StringBuilder(answer);
        sb.append("\n").append(answer.equals("YES") ? cnt : pq.poll());
        System.out.print(sb);
    }
}

 

 

4) 추가 문제

미들러 - 카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

 

챌린저 - 우주 탐사선

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