[BOJ 17422] 지폐가 넘쳐흘러

문제

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

17422번: 지폐가 넘쳐흘러

 

---

알고리즘

• 트리DP
• 우선순위 큐

---

풀이

트리와 각 금고의 지폐의 개수 \(W_{i}\)가 주어졌을 때, 두 배열 \(A, B\)를 만들어 다음과 같이 정의합니다:

 

• \(A_{i}:\) \(i\)을 루트로 하는 서브트리 안에 있는 한 리프 노드로부터 \(n\)까지의 경로에 있는 지폐 개수의 최대값.
• \(B_{i}:\) \(i\)을 루트로 하는 서브트리 안에 있는 지폐 개수의 합.

한 금고를 루트로 삼아 지폐를 떨어뜨려 쌓이게 할 때 가장 많이 쌓인 것은 한 정점을 지나는 경로에 있는 지폐 개수의 최대값, 즉, \(\max_{1 \leq i \leq N} B_{i}\)가 됩니다.

 

즉, \(A\)와 \(B\)에 대한 점화식을 다음과 같이 세울 수 있습니다:

$$A_{i} = W_{i} + \max \begin{cases}
A_{2i}\\
A_{2i + 1}
\end{cases}$$

$$B_{i} = W_{i} + A_{2i} + A_{2i + 1}$$

 

각 \(B_{i}\)의 업데이트된 값을 저장하는 \(Q_{1}\), 각 \(B_{i}\)의 업데이트 전의 값을 저장하는 \(Q_{2}\), 이렇게 두 개의 우선순위 큐를 만듭니다. (정렬을 내림차순, 즉 가장 큰 수가 가장 앞에 있습니다.)

 

먼저, 처음 트리를 순회하면서, 각 \(B_{i}\)마다 \(Q_{1}\)에 넣어 최초의 값을 출력합니다.

이후, 각 \(Q\)번의 놀이(?)마다 입력받은 \(i, D_{i}\)에 대하여 다음 작업을 수행합니다:

 

1. \(W_{i}\)를 \(D_{i}\)로 바꿉니다.
2. \(i\)를 자식으로 갖는 모든 부모 노드 \(j\)에 대하여 \(B_{j}\)를 \(Q_{2}\)에 \(\text{push}\)하고, 위의 두 점화식을 이용해 \(A_{j}\)와 \(B_{j}\)를 업데이트 한 다음 \(B_{j}\)를 \(Q_{1}\)에 \(\text{push}\)합니다.
3. \(Q_{2}\)에 값이 존재하는 동안 \(Q_{1}\)의 \(\text{top}\)값과 \(Q_{2}\)의 \(\text{top}\)값을 비교합니다. 만약, 두 값이 같다면 그 값은 이미 업데이트가 되어 존재하지 않는 값이므로 둘 다 \(\text{pop}\)을 해줍니다.
4. 두 큐의 \(\text{top}\)값이 다를 때 빠져나와 \(Q_{1}\)의 \(\text{top}\)값을 출력해줍니다.

시간복잡도: \(O(N)\)

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, Q;
ll input[300003], A[300003], B[300003];
priority_queue<ll> pq, cpq;

void solve(int cur) {
    ll l = 0, r = 0;
    if (cur * 2 <= N) {
        solve(cur * 2);
        l = A[cur * 2];
    }
    if (cur * 2 + 1 <= N) {
        solve(cur * 2 + 1);
        r = A[cur * 2 + 1];
    }
    B[cur] = input[cur] + l + r;
    pq.push(B[cur]);
    A[cur] = input[cur] + max(l, r);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for (int i = 1; i <= N; ++i) cin >> input[i];

    solve(1);

    cout << pq.top() << '\n';
    
    cin >> Q;
    while (Q--) {
        int a, b;
        cin >> a >> b;
        input[a] = b;
        while (a) {
            ll l = (a * 2 > N ? 0 : A[a * 2]), r = (a * 2 + 1 > N ? 0 : A[a * 2 + 1]);
            cpq.push(B[a]);
            B[a] = input[a] + l + r;
            A[a] = input[a] + max(l, r);
            pq.push(B[a]);
            a /= 2;
        }
        while (!pq.empty() && !cpq.empty() && pq.top() == cpq.top()) {
            pq.pop();
            cpq.pop();
        }
        cout << pq.top() << '\n';
    }

    return 0;
}