[DFS] BOJ 17501 수식 트리

문제 링크 : www.acmicpc.net/problem/17501

17501번: 수식 트리

예제 1을 수식 트리로 나타내면 아래와 같다.

노드 1 ~ 5의 피연산자 노드를 각각 미지수 X1 ~ X5로 두었을 때,

이 수식 트리의 최종 결과값은 (X1 + X3 + X5) - (X2 + X4)가 된다.

즉, 트리의 형태와 상관없이 각 리프 노드(피연산자 노드)까지 도달했을 때, 해당 피연산자가 최종 식에서 어떤 부호를 갖는지만 파악하면 문제를 쉽게 해결할 수 있다.

만약 최종 식에서 어떤 피연산자의 부호가 (-)라면, 그 값이 최소일수록 최종 값은 최대가 될 것이므로

문제에서 주어진 피연산자 값들을 정렬한 후 왼쪽 끝, 오른쪽 끝에 포인터를 두어 각 피연산자 미지수에 부여한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
typedef long long ll;
typedef pair<ll, int> p;
 
int n, lp, rp;
int tree[200010][3];        //0 : 좌항, 1 : 우항, 2 : -값
vector<int> elements;
 
int dfs(int node, int m) {
    //리프 노드인 경우 (즉, 피연산자 노드인 경우)
    if (node <= n) {
        //리프 노드까지 도달했을 때의 m값을 곱한다.
        //m은 루트부터 현재 노드의 최종 부호이다.
        if (m < 0) return elements[lp++];
        return elements[rp--];
    }
 
    //연산자 노드인 경우, 양쪽 자식에 대해 재귀한다.
    //이 때, 우측 자식에 대해서만 m값에 현재 노드의 값(+-1)을 곱해준다.
    int left_res = dfs(tree[node][0], m);
    int right_res = dfs(tree[node][1], m * tree[node][2]);
 
    if (tree[node][2] < 0) return left_res - right_res;
    return left_res + right_res;
}
 
void init() {
    int val, l, r;
    char type;
    string input;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> val;
        elements.push_back(val);
        tree[i][2] = 1;
    }
 
    for (int i = n + 1; i < 2 * n; i++) {
        cin >> type;
        cin >> l >> r;
        tree[i][0] = l;
        tree[i][1] = r;
        if (type == '-') tree[i][2] = -1;
        else tree[i][2] = 1;
    }
 
    sort(elements.begin(), elements.end());
    rp = n - 1;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    int root = 2 * n - 1;
    int answer = dfs(root, 1);
    printf("%d\n", answer);
 
    //system("PAUSE");
    return 0;
}