99클럽 코테 스터디 21일차 TIL + 힙(C++)

문제

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

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

 

코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, H, T; // 거인 수, 센티 키, 뿅망치 횟수
    cin >> N >> H >> T;

    priority_queue<int, vector<int>> pq;

    while (N--) {
        int tmp;
        cin >> tmp;
        pq.push(tmp);
    }

    // 처음부터 센티 키가 가장 큰 거인의 키보다 크다면
    if (pq.top() < H) {
        cout << "YES\n" << 0;
        return 0;
    }

    for (int i = 1; i <= T; i++) {
        int max = pq.top();

        if (max > 1) {
            pq.pop();
            pq.push(max / 2);
        }

        if (pq.top() < H) {
            cout << "YES\n" << i;
            return 0;
        }
    }

    cout << "NO\n" << pq.top();

    return 0;
}

 

풀이

내림차순으로 정렬되는 우선순위 큐(최대 힙)를 생성해 원소를 N개 저장한 다음,

T번만큼 반복을 돌면서 pq.top()을 2로 나눈 값을 큐에 삽입한 후, pq.top()이 H보다 크다면 “YES”와 반복을 돈 횟수를 출력하고 종료한다.

만약 반복문을 다 돌고나서도 pq.top()이 H보다 작거나 같으면 “NO”와 pq.top()을 출력하고 종료한다.

 

주의할 점

처음부터 H가 pq.top보다 큰 상황을 고려해야 한다!!

⇒ 첫 뿅망치를 때리기 전, 즉 for문을 돌기 전에 pq.top()과 H를 비교해 H가 크다면 “YES”와 0을 출력하고 종료한다.