BOJ 13325 - 이진 트리

[이전 블로그의 글]

각 노드에서 리프 노드까지의 거리가 (왼쪽으로 가든지, 오른쪽으로 가든지) 같도록 조정하는 것이므로 재귀를 생각할 수 있다.

이를 해결할 작은 문제로 재귀의 중간 과정부터 생각했다.

왼쪽과 오른쪽의 길이가 달라져서 조정이 필요한 상황은 "왼쪽 != 오른쪽" 이다. 이를 조정하는 작업은 더 작은 쪽에 가중치를 증가시키는 것이다.

가중치는 보정을 위해 추가하는 것이므로, 맞추고자 하는 차이만큼 증가시키면 된다.

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 987654321
	typedef long long lld;
	int n;
	int a[(1<<21)+1];
	int f(int pos){
	int l = 2 * pos + 1;
	int r = l + 1;
	// is leaf
	if(l > n || r > n) return a[pos];
	int lsum = f(l), rsum = f(r);
	if(lsum < rsum){
	a[l] += rsum - lsum;
	}
	else if(lsum > rsum){
	a[r] += lsum - rsum;
	}
	return a[pos] + max(lsum, rsum);
	}
	int main(){
	int k;
	scanf("%d", &k);
	n = (1<<(k+1))-1-1;
	for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
	f(0);
	int ans = 0;
	for(int i=1; i<=n; ++i) ans += a[i];
	printf("%d", ans);
	return 0;
	}

view raw boj-13325.cpp hosted with ❤ by GitHub