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

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

1024 MB

1869

625

506

33.488%

문제

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

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

센티가 꺼내 들은 마법 도구는 바로 마법의 뿅망치로, 이 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 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

 

풀이

힙 자료구조를 구현해 풀이하면 된다.

우선순위 큐를 이용하여 풀이했다.

 

문제 자체가 힌트가 다 주어져있다. 가장 큰 키부터 망치로 떄려서 절반으로 줄인다고 했으니

단순히 최대힙에서 루트 노드 데이터를 가져와 절반으로 나누고 다시 넣어주면 된다.

그리고 반복문에서 때리려는 거인의 키가 1이거나 센티가 더 크다면 break 해주면 된다.

 

출력문에서 원하는 그대로 루트 노드의 데이터가 센티의 키보다 작다면 yes 와 count 를, 크다면 no와 루트노드의 값을 출력하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Integer.parseInt(st.nextToken());
        long  H = Integer.parseInt(st.nextToken());
        long T = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)-> o2-o1);
        int count =0;
        for(int i=0; i<N; i++){
            queue.add(Integer.valueOf(br.readLine()));
        }
        for(int i=0; i<T;i++){
            if(queue.peek()<H || queue.peek()==1){
                break;
            }
            queue.add(queue.poll()/2);
            count++;
        }
        if(queue.peek()<H){
            System.out.println("YES");
            System.out.println(count);
        }
        else if(queue.peek()>=H){
            System.out.println("NO");
            System.out.println(queue.peek());
        }
    }
}

시간복잡도는 반복문이 상수회 돌고 있기 때문에 O(1) 로 표기할 수 있다.