[BOJ/백준][Gold4] 13325 : 이진 트리 (C++)

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

13325번: 이진 트리

[난이도] Gold4
[유형] 재귀

[풀이]
재귀함수를 이용해 left와 right 자식의 높이를 비교해서 낮은 쪽이 높은 쪽과 같아지도록 수정한다.

 

#include <cstdio>
int k,last,a[1<<21];
long long ans;
int sol(int n){
    if((1<<k)-1 <= n && n < last) return 0;
    int l = sol(n*2+1),r = sol(n*2+2);
    if(a[n*2+1]+l<a[n*2+2]+r) a[n*2+1] = a[n*2+2]+r-l;
    else a[n*2+2] = a[n*2+1]+l-r;
    ans += a[n*2+2]+a[n*2+1];
    return l+a[n*2+1];
}
int main(){
    scanf("%d",&k);
    last = (1<<(k+1))-1;
    for(int i=1;i<last;i++) scanf("%d",&a[i]);
    sol(0);
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13325.cpp