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

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

 

 

이 문제는 N명의 거인의 키가 주어지고 센티의 키, 뽕망치를 사용할 수 있는 횟수가 주어진다.

 

이때 뿅망치를 거인에게 사용하면 거인의 키가 2로 나눠진다. 이때 센티의 키가 거인의 키보다 큰 경우와 작은 경우를 나눠서 YES, NO를 출력하는 문제이다. 

 

사실 문제에서 힌트를줬다고 생각을 한다. "매번 가장 키가 큰 거인 가운데 하나를 때린다" 매번 뿅망치를 사용할때 가장 큰 거인만 때리는 것이 센티보다 더 작은 거인을 만들기 위한 효율적인 방식이기 때문이다.

 

 

이때 매번 가장 큰 거인을 찾기 위해서 최대힙을 사용하였으며 가장 먼저 나온 친구가 큰 거인이기 때문에 계속해서 2로 나눠주었다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, H, T;
priority_queue<int, vector<int>> pq;
int cnt;

/*
    YES일 경우 -> 최소 횟수 출력
    NO일 경우 -> T번 횟수 이후에 키가 가장 큰 거인 키 출력
*/

void solve() {
    bool flag = false;

    while(T--) {
        if(pq.top() == 1) {
            continue;
        }

        if(pq.top() < H) {
            flag = true;
            break;
        }

        int x = pq.top();
        pq.pop();
        x /= 2;
        pq.push(x);
        cnt++;
    }

    if(pq.top() < H) {
        flag = true;
    }

    if(flag) {      // 센티보다 다 작음
        cout << "YES" << endl << cnt;
    }
    else {
        cout << "NO" << endl << pq.top();
    }
}

void input() {
    cin >> N >> H >> T;

    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        pq.push(a);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

solve함수를 살펴보자

void solve() {
    bool flag = false;

    while(T--) {
        if(pq.top() == 1) {
            continue;
        }

        if(pq.top() < H) {
            flag = true;
            break;
        }

        int x = pq.top();
        pq.pop();
        x /= 2;
        pq.push(x);
        cnt++;
    }

    if(pq.top() < H) {
        flag = true;
    }

    if(flag) {      // 센티보다 다 작음
        cout << "YES" << endl << cnt;
    }
    else {
        cout << "NO" << endl << pq.top();
    }
}

 

뿅망치 횟수만큼 반복해서 가장 큰 친구만 때려서 / 2로 해준다. 이후 가장 큰 거인의 키가 센티의 작은 경우는 YES를 출력한다.