13325 - 이진 트리

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

2016 ACM-ICPC 한국 인터넷 예선 A번

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

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

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

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

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;

int n;
int a[(1<<21)+1];

int leftPos(int pos){ return 2*pos+1; }
int rightPos(int pos){ return leftPos(pos)+1; }

int f(int pos){
    int l = leftPos(pos), r = rightPos(pos);
    // 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;
}