[BOJ] 17501 - 수식 트리

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

BOJ - 수식 트리

문제 유형: 트리, 그래프, 그리디, 정렬

문제 난이도: Gold II

시간 제한: 1초

메모리 제한: 256MB

 

문제

수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다.

연산자 노드는 항상 두 개의 자식 노드를 가지며 연산자로 '+' 또는 '-' 를 가집니다.

피연산자 노드는 아무 자식도 가지지 않고 하나의 정수를 가집니다.

수식 트리의 계산은 다음과 같이 진행됩니다.

1. 2개의 피연산자 노드를 자식으로 가지는 연산자 노드를 하나 선택합니다.
2. 해당 노드의 연산자가 '+' 인 경우, 연산자 노드를 피연산자 노드로 바꾸고 값을 왼쪽 노드의 값과 오른쪽 노드의 값을 더한 값을 가지도록 합니다. 해당 노드의 연산자가 '-' 인 경우, 연산자 노드를 피연산자 노드로 바꾸고 값을 왼쪽 노드의 값에서 오른쪽 노드의 값을 뺀 값을 가지도록 합니다.

위의 과정을 N-1번 진행하면 하나의 수만 남고 이것이 수식의 결과가 됩니다.

진수는 계산을 시작하기 전에 초기 수식 트리의 두 개의 피연산자 노드를 골라 두 피연산자 노드가 가지는 정수를 서로 바꿀 수 있습니다. 오늘 진수가 할 일은 수식 트리가 주어지면 노드에 있는 정수를 원하는 만큼 바꾸어 수식 트리의 결과값이 최대가 되도록 하는 것입니다.

그런데 수식이 너무 큰 나머지 손으로는 계산하기가 힘듭니다. 진수를 도와주세요.

 

입력

첫 번째 줄에 정수 N (2 ≤ N ≤ 100,000) 이 주어집니다.

다음 N개의 줄에는 1번부터 N번 피연산자 노드가 가지는 정수 ai (-10,000 ≤ ai ≤ 10,000) 가 주어집니다.

그 다음 N-1 개의 줄에는 N+1번 연산자 노드부터 2N-1번 연산자 노드들의 정보가 주어집니다.

각 줄에는 연산자 노드가 가지는 연산자 oi (oi ∈ {'+', '-'}) 와 왼쪽 자식 노드의 번호와 오른쪽 자식의 번호 ci,1, ci,2 (1 ≤ ci,1, ci,2 ≤ 2N-2) 가 차례대로 주어집니다.

주어진 입력은 계산이 가능한 올바른 트리임이 보장됩니다.

 

출력

첫 번째 줄에 피연산자 노드가 가지는 정수들을 바꾸어 만들 수 있는 결과 중 최댓값을 출력합니다.

 

풀이

루트부터 bfs하면서, 하위 노드들에 자신에게 -가 얼마나 곱해졌는지를 전파한다.

왼쪽 자식에게는 이전에 곱해진 -의 개수를,

오른쪽 자식에게는 이전에 곱해진 -의 개수에 현재 자신도 -라면 그것까지 더해서 전파한다.

 

최종적으로 리프노드에 전파된 -의 개수가 홀수이면 음수, 짝수이면 양수인 것이다.

수식을 분배법칙으로 모두 풀어낸것이라고 볼 수 있다.

이제, 적절하개 수들을 배치하면 되는데, 가장 작은 수들부터 음수인 노드들에 붙인다고 생각하고, 나머지는 그대로 더한다고 생각하면, -가 붙는 수의 개수가 k개라고 하면, -(가장 작은 수 k개들의 합) + (나머지 수들)이라고 할 수 있다.

이 결과를 출력하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> sign(2 * n, 0);  // even: positive, odd: negative
    vector<int> sign_propagate(2 * n, 0);
    vector<int> nodes(n + 1);
    vector<vector<int>> adj(2 * n);

    for (int i = 1; i <= n; i++) {
        cin >> nodes[i];
    }

    for (int i = n + 1; i < 2 * n; i++) {
        char o;
        int l, r;
        cin >> o;
        cin >> l >> r;

        if (o == '+') {
            sign[i] = 0;
        } else {
            sign[i] = 1;
        }

        adj[i].push_back(l);
        adj[i].push_back(r);
    }

    queue<int> q;
    q.push(2 * n - 1);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        if (!adj[curr].empty()) {
            int left = adj[curr][0];
            int right = adj[curr][1];
            sign_propagate[left] = sign_propagate[curr];
            sign_propagate[right] = sign_propagate[curr] + sign[curr];
            q.push(left);
            q.push(right);
        }
    }

    int negatives = 0;
    for (int i = 1; i <= n; i++) {
        negatives += sign_propagate[i] % 2;
    }
    sort(nodes.begin() + 1, nodes.end());

    int ans = 0;
    for (int i = 1; i <= negatives; i++) {
        ans += nodes[i] * -1;
    }
    for (int i = negatives + 1; i <= n; i++) {
        ans += nodes[i];
    }
    cout << ans << "\n";

    return 0;
}