BOJ 23578 : 비 오는 날

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

---

코드

#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);

    int n;
    cin >> n;
    if(n == 1) {
        cout << 0;
        return 0;
    }
    vector<pii> ve(n);
    ll ans = 0;
    priority_queue<pii, vector<pii>, greater<pii>> _pq;
    for(int i = 0; i < n; i++) {
        cin >> ve[i].first;
        ve[i].second = 1;
        ans += ve[i].first;
        _pq.push({ve[i].first * 3, i});
    }

    for(int i = 0; i < n-2; i++) {
        auto [a, b] = _pq.top(); _pq.pop();
        ve[b].second++;
        ans += a;
        _pq.push({(2*ve[b].second+1)*ve[b].first, b});
    }
    cout << ans;

    return 0;
}

---

풀이

각 노드를 막대가 하나 달린 막대사탕으로 생각해보자.

이 막대사탕의 막대 끝을 다른 막대사탕의 사탕 부분에 꽂는다고 생각해보자.

이때 가장 불만이 적게 증가하는 사탕 부분에 꽂을 것이다. 

N-2번의 연결을 완료하고 나면 막대 사탕의 끝 부분이 두 개가 남는다.

이 둘을 서로 연결하면 불만의 증가 없이 연결할 수 있다.

 

위의 과정에서 어떤 막대를 꽂는지는 전혀 중요하지 않다는 사실을 알 수 있다.

 더해질 불만을 pq로 관리하면 가장 불만이 적게 증가하는 노드를 쉽게 찾을 수 있다.