[백준] 13325: 이진 트리 - JAVA

in Algorithm on 트리

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

풀이

포화이진트리의 에지들에 가중치가 있을 때, 에지들의 가중치를 증가하여 루트에서 리프까지의 거리가 같게 만들어야 한다.

트리의 높이 k 가 주어지는데 이때 트리의 사이즈는 Math.pow(2, k + 1) - 1 이다.

사이즈만큼 배열을 만들어 arr[2]부터 채운다.

arr[1]은 루트노드로 값은 0이다.

문제에서는 에지에 가중치가 있다고 표현하고있지만 각 노드들에 가중치를 넣었다.

배열을 채운 후, 루트노드 1 부터 시작하여 dfs탐색을 통해 값을 더한다.

왼쪽 자식 노드와 오른쪽 자식 노드의 값 중 큰 값을 현재 노드의 값에 더해 부모 노드로 반환하고,

답을 저장하는 변수에 현재 노드의 값과 왼쪽 자식, 오른쪽 자식의 차를 더한다.

즉, 왼쪽 자식, 오른쪽 자식 중 작은 것을 증가시켜 같은 값으로 만든다는 것이다.

리프 노드에 도달하면 리프 노드의 값을 답에 더하고, 부모 노드로 반환한다.

메모리: 148340KB

시간: 528ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static int k, size, ans;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        k = Integer.parseInt(br.readLine());
        size = (int) (Math.pow(2, k + 1) - 1);

        arr = new int[size + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 2; i < size + 1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        ans = 0;
        dfs(1);

        System.out.println(ans);
    }

    private static int dfs(int node) {
        if (node * 2 >= size) {
            // 리프노드의 값을 더해주고 반환한다
            ans += arr[node];
            return arr[node];
        }

        int left = dfs(node * 2);
        int right = dfs(node * 2 + 1);

        // 현재 노드의 값과 자식 노드들의 차이를 더해준다
        ans += arr[node] + Math.abs(left - right);
        return arr[node] + Math.max(left, right);
    }

}