[백준/BOJ] 백준 13325번 : 이진 트리

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

13325번: 이진 트리

 

부모노드에서 자식노드 쪽으로 연결되는 트리를 만들고, 이를 이용해서 루트노드(1번 노드)에서 시작해서 리프 노드까지 이동하면서, 각 노드에서 리프노드로 가는데 거리의 최댓값을 max_leaf_cost[노드 번호]에 저장해 놓는다.

그리고 이 과정에서 루트노드에서 리프노드까지 최댓값(max_leaf_cost[1])도 구할 수 있으므로 해당 값으로, 루트노드에서 모든 리프노드까지 거리를 맞춘다. 이때, 거리를 맞추기 위해 간선의 값을 변경시키는 과정은, 루트에서 가까운 간선부터 max_leaf_cost값을 확인해보며 간선 값을 증가시킬 수 있는 간선을 증가시키는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int k;
int n;
vector<pair<int, int>> tree[2100000]; //[노드 번호(최대 2의 21승 - 1)] = (가중치, child 노드 번호)
int max_leaf_cost[2100000]; //[노드 번호] = 해당 노드 번호가 루트인 서브트리에서 leaf 노드로 가는데, 거리의 최댓값
int result = 0;

int make_max_leaf_cost(int here) {

	//리프노드에 도달 했을때
	if (tree[here].size() == 0) {
		return 0;
	}

	int ret = 0;
	for (int i = 0; i < tree[here].size(); i++) {
		int cost = tree[here][i].first;
		int there = tree[here][i].second;

		ret = max(ret, make_max_leaf_cost(there) + cost);
	}
	max_leaf_cost[here] = ret;

	return ret;
}

//here노드부터 리프노드까지 거리의 합이 make_value가 되도록 간선을 수정한다
//루트노드부터 가까운 노드의 간선부터 확인해야, 가중치들의 총합이 작게 나온다
void solve(int here, int make_value) {

	for (int i = 0; i < tree[here].size(); i++) {
		int cost = tree[here][i].first;
		int there = tree[here][i].second;
		int there_max_leaf_cost = max_leaf_cost[there];

		result += cost; //기존 가중치 값
		int add_value = make_value - (there_max_leaf_cost + cost); //here과 there이 이어지는 간선에 추가되는 값
		result += add_value;
		solve(there, make_value - (cost + add_value));
	}

}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);;

	cin >> k;
	n = pow(2, k + 1) - 1; // 전체 노드의 개수

	for (int i = 2; i <= n; i++) {
		int cost;
		cin >> cost;

		int child = i;
		int parent = i / 2;

		tree[parent].push_back(make_pair(cost, child));
	}

	//루트부터 시작해서, 서브트리에서 leaf 노드로 가는데, 거리의 최댓값을 구한다.
	int root_max_leaf_cost = make_max_leaf_cost(1);

	//루트부터 시작해서, 모든 리프노드에 도달하는 가중치의 합이 root_max_leaf_cost이 되도록 만든다
	solve(1, root_max_leaf_cost);

	cout << result;

	return 0;
}