BOJ 백준 17501번 수식 트리

 

BOJ 백준 17501 수식 트리

 

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

17501번: 수식 트리

 

N개의 피연산자 노드와 N-1개 연산자 노드로 구성된 이진트리에서 피연산자 노드 정수 값을 원하는 만큼 서로 바꿨을 때 나올 수 있는 수식 트리의 최댓값을 구해야 한다.

 

 

 

문제에서는 노드에 있는 정수를 원하는 만큼 바꾸어서 수식 트리의 결과값이 최대가 되도록 한다고 서술했지만, 관점을 달리 바라보면 처음부터 트리를 구성할 때 원하는대로 노드의 정수값을 정해줘도 된다.

 

문제를 풀기 전에 우선 간단한 예시를 생각해 봤다. 하나의 부모와 두 자식으로 이루어진 간단한 트리에서 연산자 노드가 어떤지에 따라 피연산자 노드를 어떻게 구성해야 하는지를 살펴보자.

 

 

연산자 노드가 ‘+’이면 왼쪽, 오른쪽 자식 구분 없이 피연산자 노드에는 무조건 가능한 큰 수가 오면 수식 트리의 값이 최대가 된다. 반면에 연산자 노드가 ‘-‘이면 왼쪽 자식에는 가능한 큰 수, 오른쪽 자식에는 가능한 작은 수가 와야 된다.

 

 

 

그러면 조상의 영향을 받을 수 있는, 다시 말해 두 개 이상의 ‘-‘ 연산자의 영향을 받는 피연산자 노드에는 어떠한 값이 와야 되는지를 알아봐야 한다. 이를 위해 주어진 수식 트리를 괄호가 쓰일 수 있는 일반적인 연산식으로 변환하여 생각했다.

 

아래와 같은 수식 트리가 있다고 가정했을 때 이를 식으로 바꾸면 다음과 같다.

 

 

A + B - (C - (D - E))

 

그런데 괄호가 있는 모든 식은 괄호가 없는 식으로 변환이 가능하다. 그래서 위 식의 괄호를 모두 풀어주면 아래의 식이 나온다.

 

A + B - C + D - E

 

식의 괄호를 모두 풀어주면 이제 수식 트리의 최댓값을 구하기 쉬워진다. 괄호를 다 푼 연산식에서 ‘+’ 연산자 뒤에는 가능한 큰 수를, ‘-‘ 연산자 뒤에는 가능한 작은 수를 배치할수록 전체 계산값은 커진다. 여기서 괄호를 풀 때 각 피연산자가 ‘-‘를 짝수 번 만나면 ‘+’로 되는데, 이는 수식 트리에서 루트 노드부터 해당 피연산자 노드까지 ‘-‘ 연산자 노드의 오른쪽 자식으로의 이동을 짝수 번 거치면 결과적으로 ‘+’ 연산자가 된다는 말과 동치이다.

 

 

 

종합하여 정리하면 다음과 같다.

 

 

 

‘-‘의 오른쪽 자식으로의 이동을 홀수 번 탔을 때 나오는 피연산자 노드에는 가능한 작은 수를, 나머지는 모두 가능한 큰 수를 배치한다.

 

 

 

배치하는 과정에서 가능한 작은 수 또는 큰 수를 구하는 건 간단하다. 수식 노드 탐색 전에 피연산자 노드 값들만 리스트로 모아서 정렬한 후 두 개의 인덱스를 사용하여 배치할 때마다 각 인덱스를 1만큼 증가 또는 감소해주면 된다.

 

 

 

아래 예시는 이를 적용한 과정을 그림으로 도식화한 것이다. 간선에서의 ‘작’이 ‘-‘의 오른쪽 자식으로의 이동을 의미한다. 피연산자 노드 C와 E는 ‘작’을 홀수 번 거치므로 (C는 1번, E는 3번) 각각 15, 20을, 나머지에는 50, 40, 25를 배치하면 수식 트리의 최댓값이 80으로 나온다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const int N_MAX = (int)1e5;

int n, front, rear;
int oper[N_MAX * 2 + 1];
int leftChild[N_MAX * 2 + 1];
int rightChild[N_MAX * 2 + 1];
int parent[N_MAX * 2 + 1];
vector<ll> a;

ll getMaxResult(int now, int subCnt){
    ll ret = 0;
    // 연산자 노드이면
    if (now >= n + 1 && now < n * 2){
        // 현재 노드의 연산자가 '+'이면
        if (oper[now] == 1){
            // 왼쪽 자식
            ret += getMaxResult(leftChild[now], subCnt);
            // 오른쪽 자식
            ret += getMaxResult(rightChild[now], subCnt);
        }
        // 현재 노드의 연산자가 '-'이면
        else {
            // 왼쪽 자식
            ret += getMaxResult(leftChild[now], subCnt);
            // 오른쪽 자식
            ret -= getMaxResult(rightChild[now], subCnt + 1);
        }
    }
    // 피연산자 노드이면
    else {
        // 빼기 연산자가 홀수 번 작용하면
        if (subCnt % 2){
            ret = a[front++];
        }
        else {
            ret = a[rear--];
        }
    }
    return ret;
}

int main(){
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    
    cin >> n;
    for (int i = 0; i < n; i++){
        ll x; cin >> x;
        a.push_back(x);
    }
    
    sort(a.begin(), a.end());
    front = 0; rear = (int)a.size() - 1;
    
    for (int i = n + 1; i < n * 2; i++){
        char o; int c1, c2;
        cin >> o >> c1 >> c2;
        oper[i] = (o == '+') ? 1 : 0;
        leftChild[i] = c1; rightChild[i] = c2;
        parent[c1] = parent[c2] = i;
    }
    
    ll res = getMaxResult(n * 2 - 1, 0);
    cout << res << "\n";
    
    return 0;
}