[백준] (C++) 19683번: 센티와 마법의 뿅망치

문제

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

---

관련 개념

: 우선순위 큐

 

풀이

 뿅망치를 이용해 주어진 센티의 키보다 거인들의 키가 작아지도록 만들 수 있는지 없는지를 판단해야 하는 문제이다.

만들 수 있을 경우 뿅망치를 최소한으로 사용해야 한다는 점 (카운팅 변수 필요), 

만들 수 없을 경우 가장 큰 거인의 키를 알아내야 한다는 점에서 우선순위 큐를 사용하는 것이 적합하다.

 

뿅망치를 사용할 수 있는 횟수(문제에서 주어진 T값)로 for문을 돌린 후, 

for 문 내에서 가장 큰 거인을 뿅망치로 때리면 된다. 

 

for문 안에서 가장 큰 거인을 우선순위 큐의 top() 을 이용하여 추출하고, 

1. top()이 1보다 작거나 같은 경우 -> 더 이상 뿅망치로 때릴 수 없음
2. top()이 센티의 키보다 작은 경우 -> 모든 거인이 센티보다 작음

이 두가지의 경우 for문을 종료하면 된다. 

 

for문 종료 후 우선순위 큐의 top() 값을 검사해 

top()이 센티의 키(H값) 보다 작은지 / 크거나 같은지에 따라 정답을 출력해주면 된다. 

 

정답 코드  

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

long long int n, h, t, cnt;
priority_queue<long long int> pq; // 거인 키가 들어있는 우선순위 큐

int main() {

	cin >> n >> h >> t;
	for (int i = 0; i < n; i++) {
		long long int num;
		cin >> num;
		pq.push(num);
	}

	for (int i = 0; i < t; i++) {
		long long int top = pq.top(); // 가장 큰 거인의 키.
		if (top <= 1) break;
		if (top < h) break;
		
		// top >= h
		top = top / 2; // 문제에 키가 "반드시" 정수라는 조건이 없어서 혼란의 여지가 있음. 
		pq.pop();
		pq.push(top);
		cnt++;
	} 
	if (pq.top() < h) {
		cout << "YES" << '\n' << cnt;
	}
	else {
		cout << "NO" << '\n' << pq.top();
	}
	return 0;
}