BOJ 백준 17501번 수식 트리

BOJ 백준 17501번 수식 트리

BOJ 백준 17501 수식 트리

문제: https://www.acmicpc.net/problem/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 #include #include 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 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 << "

"; return 0; }

from http://glanceyes.tistory.com/72 by ccl(A) rewrite - 2021-08-10 15:26:15