BOJ 20666 : 인물이와 정수

• 문제 링크 : boj.kr/20666
• 난이도 : G3
• 태그 : 그리디, 우선순위 큐

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    ll n, m;
    cin >> n >> m;
    vector<ll> arr(n+1);
    vector<bool> visit(n+1, false);
    for(ll i = 1; i <= n; i++) cin >> arr[i];

    int p;
    cin >> p;
    vector<vector<pll>> tip(n+1);
    while(p--) {
        ll a, b, t;
        cin >> a >> b >> t;
        tip[a].emplace_back(pll(b, t));
        arr[b] += t;
    }
    priority_queue<pll, vector<pll>, greater<pll>> _pq;
    for(ll i = 1; i <= n; i++) _pq.push({arr[i], i});

    ll ans = 0;
    for(int i = 0; i < m; i++) {
        auto curr = _pq.top(); _pq.pop();
        if(visit[curr.second]) {
            i--;
            continue;
        }
        ans = max(ans, curr.first);
        visit[curr.second] = true;
        for(auto u : tip[curr.second]) {
            if(visit[u.first]) continue;
            arr[u.first] -= u.second;
            _pq.push({arr[u.first], u.first});
        }
    }
    cout << ans;

    return 0;
}

---

풀이

팁을 고려해서 몬스터의 최종 난이도를 산정한다. 최종 난이도를 낮은 난이도가 앞에 오도록 인덱스와 함께 우선순위 큐에 넣어 준다. 우선순위 큐의 앞에 있는 몬스터가 아직 처치하지 않은 몬스터라면 처치한다. 처치하고 팁에 따라 몬스터의 난이도를 조정한 다음 큐에 새롭게 넣어준다. M마리의 몬스터를 잡을때까지 반복한다.