[백준_19638번] 센티와 마법의 뿅망치

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

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

[문제]

 센티는 마법 도구들을 지니고 여행을 떠나는 것이 취미인 악당이다. 거인의 나라에 도착한 센티는 자신보다 키가 크거나 같은 거인들이 있다는 사실이 마음에 들지 않았다. 센티가 꺼내 들은 마법 도구는 바로 마법의 뿅망치로, 이 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 2 ⌋로 변하는 마법 도구이다. 단, 키가 1인 경우 더 줄어들 수가 없어 뿅망치의 영향을 받지 않는다.

 하지만 마법의 뿅망치는 횟수 제한이 있다. 그래서 센티는 마법의 뿅망치를 효율적으로 사용하기 위한 전략을 수립했다. 바로 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다. 과연 센티가 수립한 전략에 맞게 마법의 뿅망치를 이용한다면 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있을까?

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_19638 {
	static int n,h,t;
	static PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt(); // 거인의 수
		h=sc.nextInt(); // 센티의 키
		t=sc.nextInt(); // 뿅망치 제한 횟수
		
		// 거인키를 큰 순서대로 정렬
		for(int i=0;i<n;i++)
			pq.add(sc.nextInt());
		
		// 뿅망치 제한 횟수만큼 수행
		for(int i=0;i<t;i++) {
			int giant=pq.peek(); // 가장 키가 큰 거인 선택
			
			/*
			 * 최대힙 우선순위 큐를 사용했기 때문에 우선순위가 가장 큰(값이 가장 큰) 값보다
			 * 센티의 키가 크다면 모든 거인보다 센티의 키가 큰 경우이다.
			 * 뿅망치 제한 횟수 이전에 조건을 달성했으므로 뿅망치를 최소로 사용한 횟수(i)를 출력
			 */
			if(giant<h) {
				System.out.println("YES");
				System.out.println(i); // 뿅망치 사용 횟수
				System.exit(0);
			}
			
			/*
			 * 키가 1인 경우는 뿅망치의 영향을 받지 않기 때문에 
			 * 키가 1보다 큰 경우에만 키를 /2한 뒤 다시 삽입한다.
			 */
			else if(giant>1) {
				pq.poll();
				pq.add(giant/2);
			}
		}
		
		// 뿅망치 제한 횟수를 모두 다 사용한 경우 -> 가장 큰 거인과 센티의 키 비교
		if(pq.peek()<h) {
			System.out.println("YES");
			System.out.println(t); // 뿅망치 사용 횟수 출력
		}
		// 센티보다 큰 거인이 있는 경우
		else {
			System.out.println("NO");
			System.out.println(pq.peek()); // 가장 키가 큰 거인의 키 출력
		}
	}
}

 

[고찰]

 이번 문제 또한 어떤 자료구조를 사용하느냐가 핵심인 문제로 문제 안에서 힌트를 줘 쉽게 알아차릴 수 있는 부분이었다. "바로 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다." 부분이 바로 이에 해당한다. 매번 가장 큰 값이 선택될 수 있도록 최대힙 우선순위 큐를 사용하면 효율적으로 문제를 풀 수 있다. 

 

 처음에 짠 코드는 모든 거인보다 센티의 키가 큰지 검사하기 위해 완전탐색 방법을 사용했더니 시간초과 결과를 얻었다. 우선순위 큐를 사용해놓고 정작 자료구조의 특성을 활용하지 못한 결과였다. 좀 더 생각을 해보니 우선순위 큐에서 맨 앞에있는 값은 가장 키가 큰 거인이기 때문에 해당 값하고만 센티의 키를 비교하면 모든 거인보다 센티의 키가 큰지 알 수 있는 더 간단한 방법이 있다는 것을 깨달았다. 이렇게 코드를 고치니 정답 처리를 받을 수 있었다. 문제를 풀 때 좀더 생각하고, 이해하면서 풀어야겠다는 생각을 했다.