[BAE/<JOON> 문제풀이] 13325. 이진 트리

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

13325번: 이진 트리

 

핵심 ::

루트 정점에 근접한 정점에 비용을 추가 할 수록 전체 추가 비용이 줄어든다. ( 그 정점 아래의 모든 리프 노드에 비용이 추가되므로 )

간선에 비용을 늘릴수밖에 없으므로 가장 먼 리프 노드를 찾고 그 거리를 기준으로 다른 경로에 비용을 추가하면 된다.

 

풀이 ::

DP[x] = x 정점 아래 리프 노드 중 가장 먼 리프 노드까지의 거리

 

현재 간선에 필요한 값 = p

 

1번 정점부터 아래로 탐색하면 현재 정점에서 가능한 최대로 비용을 추가하면 된다.

 

이미 정해진 간선 비용이 있고 아래에 있는 정점 비용과 합쳤을 때 그 비용을 초과하면 안되므로

 

현재 간선에 추가할 최대 비용은 p - dp[x] 이다.

 

이 후 아래 간선에 추가 비용과 그 간선까지의 거리를 빼고 재귀 탐색하며 값을 탐색하면 된다.

 

또한 문제에서 요구하는 값이 추가 비용 합계가 아니라 그냥 전체 비용 합계니까 우선적으로 주어진 간선 비용을 더해서 출력한다.

 

의견::

트리 DP들은 작은 문제를 해결하고 그것으로 더 큰 문제를 해결한다는 부분만 있는 것 같다.

 

예전 글에 트리 DP가 왜 DP인지 모르겠다고 쓴 적이 있는데 DP는 맞지. 작은 문제 -> 큰 문제니까

 

트리 특성 상 작은 문제 부분이 겹칠 일이 잘 없어서 그랬던 것 같다.

 

다른 DP 문제들은 대부분 소문제의 공통 부분을 찾고 중복 제거 하는 식으로 풀어왔으니깐..

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

vector<int> dp;
vector<vector<int>> arr;
vector<vector<int>> t;

int re(int p) {
	int& ret = dp[p];
	if (ret != -1) return ret;
	ret = 1;
	for (const auto& nx : t[p]) {
		ret += re(nx);
	}
	return ret;
}

void maketree(int c, int p) {
	for (const auto& nx : arr[c]) {
		if (nx != p) {
			t[c].push_back(nx);			
			maketree(nx, c);
		}
	}
}

//부모정점이 없는 정점은 비용 0
vector<int> elist;
int n;

// dp[x] = x 정점 아래 경로 중 가장 큰 비용 
int tsum(int x) {
	if (x > n) return 0;
	int s1 = tsum(x * 2);
	int s2 = tsum(x * 2 + 1);
	dp[x] = s1 > s2 ? s1 : s2;
	return dp[x] + elist[x];
}

// x 정점 아래 필요한 추가 비용 합계
int r(int x, int p) {
	if (x > n) return 0;
	int d = p - dp[x];//이만큼 추가
	if (x * 2 > n) return d;
	int s1 = r(x * 2, p - (elist[x * 2] + d)), s2 = r(x * 2 + 1, p - (elist[x * 2 + 1] + d));
	return s1 + s2 + d;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0); 
	int hi; cin >> hi;
	n = (int)pow(2, hi + 1) - 1;//정점 개수
	elist = vector<int>(n + 1);
	dp = vector<int>(n + 1, 2100000000);
	int sum = 0;
	for (int i = 2; i <= n; i++) {
		cin >> elist[i];
		sum += elist[i];
	}	
	tsum(1);
	cout << sum + r(1, dp[1]) << "\n";
	return 0;
}