[백준] 8479 Godzilla (C++)

오래간만에 쓰는 문제풀이 글. 

 

오늘 999문제를 풀고 djs100201에게 1000문제 제물로 좋은 문제를 추천해달라고 했더니 추천해준 문제이다.

과제를 하기 싫기도 하고, 1000문제를 찍어서 기분이 좋기도 하고, 문제가 좋기도 하고 암튼 그래서 써본다.

 

boj.kr/8479

 

문제 좋은 것 같아요. 추천합니다 ㅎㅎ! 이런 문제는 어떻게 만드는 건지...ㄷㄷ

 

 

---

우선 문제를 이해하기가 쉽지 않았다... 영어 지문임을 감안해도 좀 못 쓴 것 같다. 고릴라 컨셉을 넣어서 그런 것 같다.

 

암튼, 문제를 요약하면...

Graph가 주어진다. 각 노드마다 사람의 수가 있다.

괴물은 매일 1번 노드에서 x번 노드에 가서 거기 있는 사람을 모두 먹는다. 이때, 1번 노드에서 x번 노드로 가는 길에 있는 사람들은 모두 죽는다. 

하루가 지날 때마다 노드에 있는 사람의 수가 1명 씩 줄어든다. 

괴물이 먹을 수 있는 최대 사람의 수는 몇 명인지를 구하는 문제이다.

 

 

---

그래서 정말 오래 고민했다. 고민 끝에 얻은 결론이 하나 있었다. 

먹기로 결정한 노드들을 모두 정해두면 그 노드들 모두 방문할 수 있다는 것이다. 말이 좀 이상한데, 만약 3번, 4번, 7번 노드에 있는 사람들을 먹기로 했다고 가정하자. 이때, 순서를 잘 조정하면 3, 4, 7 노드에 있는 사람들을 죽이지 않고 먹을 수 있다. (그러니까 각 노드를 먹기 전에 각 노드를 지나는 경우를 안 만들 수 있다는 뜻이다.)

 

그렇다면 먹을 노드들을 어떻게 정해야 할까?에 대해 생각해 보았다. 그러다가 든 생각이 그러면 그냥 사람 수가 많은 것을 먹으면 된다는 걸 느꼈다. 그렇게 정하기만 하면 알아서 잘 먹일 수 있기 때문이다.

 

오... 위의 두 사실을 합치면 사람 수가 많은 노드들부터 순서대로 먹이면 된다는 것을 알아낼 수 있다!

그러니까 결국 그래프의 모양이 어떻든 상관이 없다(...!)

 

따라서, 사람 수를 내림차순으로 정렬한 뒤, 먹일 수 있는 만큼 최대한 선택하여 먹이면 된다. (구현할 때 매일 노드의 사람 수가 한 명 씩 줄어드는 것을 잊으면 안 된다.) 근데 순서가 어떻게 되든 사람이 줄어드는 수는 같으므로 그냥 제일 큰 거부터 먹어도 선택한 노드들을 모두 먹을 수 있다고 가정하고 풀어도 상관이 없다. 

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, a, b, ans, d;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    vector<ll> v(n + 1);
    for (ll i = 1; i <= n; i++) cin >> v[i];
    sort(v.begin() + 1, v.end(), greater<>());
    for (ll i = 0; i < m; i++) cin >> a >> b;
    for (ll i = 1; i <= n; i++, d++) ans += v[i] > d ? v[i] - d : 0;
    cout << ans << '\n';
}

 

정말 좋은 문제인 것 같다.

 

두 가지의 관찰을 합쳐 엄청난 사실을 알아내었을 때 기분이 매우 좋았다.

 

9ooooooooooooood

 

1000 solve!