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

문제

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

걸린 시간

00 : 24 : 51

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, Hcenti, t;
    cin >> n >> Hcenti >> t;
    priority_queue<int, vector<int>, less<int>> Hgiant;
    int h;
    for(int i = 0; i < n; i++){
        cin >> h;
        Hgiant.push(h);
    }
    for(int i = 0; i < t; i++){
        int tallest = Hgiant.top();
        if(tallest < Hcenti){
            cout << "YES\n" << i << "\n";
            return 0;
        }
        else if(tallest > 1){
            Hgiant.pop();
            Hgiant.push(tallest/2);
        }
    }
    if(Hgiant.top() < Hcenti)
        cout << "YES\n" << t << "\n";
    else
        cout << "NO\n" << Hgiant.top() << "\n";
    return 0;
}

문제에서 매번 가장 키가 큰 거인을 뿅망치로 내려친다는 전략이 주어지지 않았으면 난이도가 조금 높아졌을듯 한 문제.

최대 힙을 사용하면 쉽게 풀이할 수 있다.

처음 문제를 접했을 때 하한 기호에 겁먹고 모두 읽지도 않은 채 다른 문제로 넘어갔었다. 쫄지말자.