[우선순위큐] 백준 19638 센티와 마법의 뿅망치 C++

 

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

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

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

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, c, t, max = 0, count = 0, temp;
    priority_queue<int> q;
    
    cin >> n >> c >> t;
    
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        q.push(temp);
    }

    for (int i = 0; i < t; i++)
    {
        max = q.top();

        if (max >= c)
        {
            if (max != 1)
            {
                max /= 2;
                q.pop();
                q.push(max);
                count++;
            }
        }
        else
        {
            printf("YES\n");
            printf("%d", count);
            return 0;
        }
    }
    
    if (q.top() < c)
    {
        printf("YES\n");
        printf("%d", count);
    }
    else
    {
        printf("NO\n");
        printf("%d", q.top());
    }
   
    return 0;
}

 

1. 첫 시도 => 시간 초과

#include<iostream>
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, c, t, max = 0, count = 0;
    
    cin >> n >> c >> t;
    int *h = new int[n];

    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
    }

    for (int i = 0; i < t; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (h[max] < h[j])
            {
                max = j;
            }
        }

        if (h[max] > c)
        {
            h[max] /= 2;
            count++;
        }
        else {
            printf("NO\n");
            printf("%d", h[max]);
            return 0;
        }
    }

    if (h[max] <= c)
    {
        printf("NO\n");
        printf("%d", h[max]);
        return 0;
    }
    printf("YES\n");
    printf("%d", count);
}