[백준] 13325번 이진 트리 (C++)

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

 

 

이 문제는 트리의 높이와 각 노드에서 연결되는 간선에 대한 가중치가 입력되었을때 루트에서 모든 리프노드로 갈때 그 가중치의 합이 같게 만들기 위한 에지들의 가중치 총 합을 출력하는 문제이다.

 

트리 구조이기 때문에 바로 dfs(깊이 우선 탐색)을 사용해야겠다고 생각은 했지만

도저히 접근을 어떻게 해야할줄 몰라서 다른 사람들의 풀이를 보았다.

 

 

자식 노드들의 왼쪽 자식 길이와 오른쪽 자식 길이를 구하여 리턴해주면 그것이 답이 되는것을 확인할 수 있었다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int K, treesize, answer;
int tree[1 << 22];

int dfs(int Node) {
    if(treesize <= Node) {
        answer += tree[Node];
        return tree[Node];
    }
    else {
        int left = dfs(2 * Node);
        int right = dfs(2 * Node + 1);
        answer += abs(left - right) + tree[Node];
        return tree[Node] + max(left, right);
    }
}

void solve() {
    dfs(1);

    cout << answer;
}

void input() {
    cin >> K;

    treesize = (2 << K) - 1;

    for(int i = 2; i <= treesize; i++) {
        cin >> tree[i];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}