[BaekJoon] 13325 이진 트리 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int height;
    static int answer;
    static int[] weights;

    static void input() {
        Reader scanner = new Reader();

        height = scanner.nextInt();
        int totalNodeCount = (int) Math.pow(2, height + 1) - 1;
        weights = new int[totalNodeCount + 1];
        for (int idx = 2; idx <= totalNodeCount; idx++) {
            weights[idx] = scanner.nextInt();
        }
    }

    /*
     * 이때 후위 탐색을 이용하여 가중치를 증가시킨다
     *  - 우선 DFS를 통해 리프 노드까지 이동하고 리프 노드에 도달하면 리프 노드의 가중치를 반환한다
     *      - 이때, 정답을 나타내는 변수에 리프 노드 가중치를 더한 후 반환한다 (모든 가중치를 더해야하므로)
     *  - 이렇게 한 노드의 왼쪽, 오른쪽 자식의 가중치를 알게 되면 두 가중치 중 더 높은 가중치와 현재 노드의 가중치를 합하여 반환한다
     *      - 결국, 루트 노드부터 리프 노드까지의 모든 경로 중 가장 가중치 합이 높은 경로의 가중치 합에 맞춰서 가중치를 증가시켜야 한다
     *      - 그러므로 아래에서부터 가중치 합을 더해나가며 더 높은 가중치의 합들을 위로 올리면서 모든 경로의 가중치의 합을 일치하도록 증가시킨다
     *      - 이때, 아래에서부터 올라온 가중치의 합이 왼쪽 서브 트리와 오른쪽 서브 트리에서 올라올텐데
     *        두 합 중 더 작은 합에 두 합의 차이만큼 증가시켜줘야 하기 때문에
     *        정답을 나타내는 변수에 현재 노드의 가중치와 두 합의 차이만큼을 더해준다
     *          - 더 합이 작은 곳에 차이만큼 증가시켜줬으니 이 차이 역시 정답에 더해줘야 한다
     *  - 이렇게 루트 노드까지 올라가며 총 노드의 가중치의 합을 구한다
     */
    static void solution() {
        calculateWeightSum(1, 0);
        System.out.println(answer);
    }

    static int calculateWeightSum(int curIdx, int curHeight) {
        if (curHeight == height) {
            answer += weights[curIdx];
            return weights[curIdx];
        }

        int left = calculateWeightSum(curIdx * 2, curHeight + 1);
        int right = calculateWeightSum(curIdx * 2 + 1, curHeight + 1);
        answer += (weights[curIdx] + Math.abs(right - left));
        return weights[curIdx] + Math.max(left, right);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}