[BOJ/20666] 인물이와 정수, c++

🔗 링크

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

20666번: 인물이와 정수

🤯 한줄 후기

visit 사랑해

🤷 문제

👩‍💻 풀이

visit 판별문 한줄이 날 힘들게 했던 문제

역시 shake! 2020 B번 문제이다.

우선순위 큐를 쓰면 편한 문제!

 

처음에 item 관계를 그래프 처럼 생각해서 연결하여 풀려고 하긴 했는데 난이도가 높아지면 큐에서 어떻게 해야할 지 모르겠어서 처음부터 다시 생각했다. 그러던 중 아예 처음부터 난이도를 올려서 시작하는게 좋을 것 같다는 생각이 들었다.

처음에는 무조건 item 없이 시작할테니 tip으로 들어온 몬스터는 난이도를 미리 올려서 큐에 넣어주었다.

큐는 { 난이도, 인덱스 } 형식으로 들어가고, 난이도를 기준으로 min heap을 만들어줬다.

 

이제 난이도가 작은 몬스터부터 top에서 나올텐데 해당 몬스터를 잡고 바로 이 몬스터를 잡으면 난이도 감소 효과를 누릴 수 있는 몬스터들을 모두 찾아서 하향시켜준다.

하향 시키고 나서 다시 큐에 넣어준다. 어차피 안에 있는 같은 몬스터를 갱신시키지 않아도 되는 이유는 min heap 이고, 난이도가 내려갔기 때문에 갱신할 필요 없이 후에 들어간 몬스터가 더 top에 가까울 것이다.

 

이 과정에서 visit 배열의 역할이 중요하다.

처음에 queue에서 나오는 몬스터만 visit 판별을 해줬더니 계속해서 TLE가 발생했다.

곰곰히 생각해보니 이미 죽은 몬스터는 나중에 어떤 아이템이 생겼다고 해서 난이도를 하향시켜줄 필요가 없다.

이게 key point 같다. 따라서 for 문에서 이미 죽은 몬스터는 난이도 연산 없이 continue 하도록 수정하였더니 AC를 받을 수 있었다.

 

주의할 점은 딱 보다 싶이 난이도가 굉장히 큰 숫자로 들어온다. 

+, - 연산이 있으니 자료형을 long long으로 해주자.

💻 코드

//TLE
//BOJ 20666 인물이와 정수
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
priority_queue<pii, vector<pii>, greater<pii>> q;
ll add[101010];
int visit[101010];
vector<pii> item[101010];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    ll maxC = 0;
    cin >> N >> M;
    for(int i=1; i<=N; i++) {
        cin >> add[i];
    }
    int p;
    cin >> p;
    for(int i=0; i<p; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add[b] += c;
        item[a].push_back({b, c});
    }
    for(int i=1; i<=N; i++) {
        q.push({add[i], i});
    }
    int cnt = 0;
    while(cnt < M) {
        pii monster = q.top();
        q.pop();
        if(visit[monster.second])   continue;
        visit[monster.second] = 1;
        for (pii temp : item[monster.second]) {
            if(visit[temp.first])   continue;
            add[temp.first] -= temp.second;
            q.push({add[temp.first], temp.first});
        }
        if(maxC < monster.first)   maxC = monster.first;
        cnt += 1;
    }
    cout << maxC;
    return 0;
}