백준 13325 이진 트리

BOJ 13325

일단, 노드 간의 가중치를 노드로 하는 새로운 트리를 만들고 다음과 같은 기본 아이디어를 적용한다. 

[어떠한 노드의 자식 노드들의 '각자의 자식 노드들의 가중치 합'은 같아야 한다]

      0

  3      2

2  3   1  3

문제의 1번예시와 비슷한 트리를 예로 들겠다.

레벨 1의 [값 3]노드가 가지고 있는 자식인 2와 3은 위의 기본 아이디어를 통해 같은 값을 가져야 한다

따라서 2는 3으로 바뀐다

또한 레벨 1의 [값 2] 노드가 가지고 있는 자식인 1과 3또한 같아야 하기 때문에 1이 3으로 바뀐다

그러면 그래프가 아래와 같이 변한다

      0

  3      2

3  3   3  3

또한 레벨 0의 노드가 가진 자식들은 가중치가 6이거나 (왼쪽), 5이다(오른쪽)

오른쪽 서브 트리가 가중치가 하나 작기 때문에 오른쪽 서브트리의 헤드, 즉 레벨 1의 [값 2]노드를 3으로 바꾸어준다

      0

  3      3

3  3   3  3

따라서 위와 같은 노드로 변한다

소스코드의 f(a, maxLevel)은 다음을 의미한다

[노드 a가 가진 자식들의 가중치들중 최대값]

위의 예시에서 두번째 상황의 트리를 예를 들면

레벨 1에서의 f()값은 [값 3] 노드의 경우 6, [값 2]노드의 경우 5가 return 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string.h>
#include <utility>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>

using namespace std;

int Nodes[4200000];

int N;

int parent(int node) {
	return (int)(node / 2);
}
int left(int node) {
	return node * 2;
}
int right(int node) {
	return node * 2 + 1;
}

int f(int node, int maxLevel) {
	if (node >= maxLevel) return 0;

	int leftsum = f(left(node), maxLevel) + Nodes[left(node)];
	int rightsum = f(right(node), maxLevel) + Nodes[right(node)];

	int m = max(leftsum, rightsum);
	int diff;
	if (leftsum > rightsum) {
		diff = (leftsum - rightsum);
		Nodes[right(node)] += diff;
	}
	else {
		diff = rightsum - leftsum;
		Nodes[left(node)] += diff;
	}
	return m;
}

int main() {
	scanf("%d", &N);

	memset(Nodes, 0, sizeof(int) * 2100000);

	int temp;
	for (int i = 2; i < pow(2, N + 1); i++) {
		scanf("%d", &temp);
		Nodes[i] = temp;
		//Nodes[i] = 1;
	}

	f(1, (int)pow(2, N + 1));

	int result = 0;
	for (int i = 0; i < pow(2, N + 1); i++) {
		result += Nodes[i];
	}
	cout << result << endl;

	return 0;
}