백준 13325 이진트리 풀이 (feat. JAVA)(R)

이거는.. 너무 어려웠다...

뭐라는거야 진짜 ㅠ 

일단 온종일 붙잡고 최대한 이해하려고 노력함..

근데 진짜 더는 머리가 안 돌아감

추후에 다시 풀어보자.. 

/*
[백준]
13325, 이진 트리

[문제파악]
- 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다.
- 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다.
- 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다.
- 이 문제에서는, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같도록 하고, 또한 에지 가중치들의 총합을 최소화 하려고 한다.
- 예를 들어, 그림 1(a)에 있는 높이 2 인 포화이진트리를 살펴보자.
- 에지 옆에 있는 수는 그 에지의 가중치를 나타낸다.
- 이 경우에 대한 답이 그림 1(b)에 나타나 있다.
- 즉, 루트에서 모든 리프까지의 거리가 5 이고, 에지 가중치들의 총합은 이 경우에 가능한 최솟값인 15 이다.
- 포화이진트리에 들어 있는 모든 에지들의 가중치가 주어졌을 때, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같게 하면서 에지 가중치들의 총합이 최소가 되도록 하는 프로그램을 작성하시오.

[입력]
- 입력 데이터는 표준입력을 사용한다.
- 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다.
- 두 번째 줄에는 모든 에지들의 가중치가 주어진다.
- 에지들의 가중치는 루트에서 가까운 레벨에 있는 것부터, 같은 레벨에 있는 경우는 왼쪽부터 오른쪽의 순서로 주어진다.
- 각 에지의 가중치는 1 이상 1,000 이하인 정수로 주어진다.

[출력]
- 출력은 표준출력을 사용한다.
- 에지들의 가중치를 증가시킨 다음에 얻어지는 트리에 있는 모든 에지들의 가중치들의 총합을 한 줄에 출력한다.
- 어떤 에지의 가중치는 경우에 따라 1,000 이상의 값으로 증가될 수도 있다는 점에 유의하시오.

[구현방법]
- 문제를 읽어보니 각각 경로에 대해 가중치가 다른데, 이 경로들을 타고 가서 리프 노드에 쌓이는 가중치가 모든 리프 노드마다 똑같길 바란다는 의미임
- 그리고 같길 바라니까 경로마다 가중치를 바꿔도 되긴하는데 전체적으로 그게 모두 동일하길 바란다는 의미
- 이거는 모든 노드는 도달하기까지 각각의 고유 경로를 가지게된다 (왜냐면 이진트리라서 다른 경로로 우회할 수 없음)
- 즉, 각 모든 노드에 도달할 수 있는 경로를, 그 가중치의 순서를 기록한다음 전체 합이 최솟값이 되도록 변경해야한다
- 각 리프노드에서 가장 가까운 순으로 변경하기엔 무리가 있는게 최상단에 있는 리프 노드 한개에 +1을 하는게 모든 노드에 전반적으로 +1을 해주는 효과도 있기 때문에 잘 따져야한다
- 근데 이게 분명 공식같은게 있을건데 이걸 모르니까 뭐 어케 접근해야하는지 몰겠네 (like 수학공식 몰라서 못 푸는 유형)
- 일단 문제 특성상 DP? 무조건임 ㅋㅋㅋ 기록해둬야함 어디다가
- 그러면 각 노드에 도달하기까지의 값을 기록해두고 그걸 비교해서 더하고 빼야하나?
- 약간 최대값 리프 노드 찾고 걔한테 맞추는거지 큰놈을 줄일 수는 없으니
- 근데 일단 이걸 하려면 이진 트리 입력 받을 줄 알아야...

[보완점]
- 30분 고민했는데 못 풀어서 답을 확인해봤는데(나만의 룰), 어처구니 없게 쉬움
- 일단 트리 구조 필요 없음 (간선만 저장하면 되서 풀이식을 트리처럼 구현해두면 될뿐 트리는 필요없다..) -> 1차 충격
- DFS로 타고 들어가면서 DP와의 차이를 구해 더하는 식으로 진행하면 됨..
- 또한 포화이진트리는 간선의 갯수를 구하는 그 고유의 공식을... 사용... (2^(K+1) - 1)
-
*/

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

public class Main {
    static int edgeCount, k, result;
    static int[] DP;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        edgeCount = (int) Math.pow(2, k + 1) - 1;  // 포화이진트리의 노드 갯수 구하는 공식
        DP = new int[edgeCount + 1];

        // 2번 노드부터 시작이니까 i는 2부터 시작 (1번은 root 노드라 간선이 없기 때문임)
        for(int i = 2; i <= edgeCount; i++) {
            DP[i] =Integer.parseInt(st.nextToken());
        }

        DFS(1,0);

        System.out.println(result);
    }

    static int DFS(int idx, int height) {
        // 리프 노드에 도달하면 결과값에 그간 DP 값을 결과(result)에 누적하고 리턴
        if(height == k) {
            result += DP[idx];
            return DP[idx];
        }

        // DFS로 왼쪽과 오른쪽 서브트리의 가중치 합을 구하고 비교 (가중치 차이 보정 및 최소 가중치로 맞추기 위함)
        int left = DFS(idx * 2, height + 1);
        int right = DFS(idx * 2 + 1, height + 1);

        // 왼쪽과 오른쪽 가중치의 차이를 보정하고 해당 간선의 가중치까지 결과에 누적
        // 이게 가중치를 더한게 무슨 의미인지 아래에 잠깐 풀자면~ (*)
        result += DP[idx] + Math.abs(left - right);

        // 최대 경로 가중치를 반환 (상위 노드에서 사용하기 위함임)
        return DP[idx] + Math.max(left, right);
    }
}
/*
약간 이런 의미이다
예를들어 왼쪽이 누적 가중치가 4이고, 오른쪽 가중치가 10이라면?
이때 가중치 차이는 6이다 (너무 당연하게도)

나는 처음에 어떤 간선을 몇만큼 수정해야하는지를 하나하나 다 알아야한다고 생각했지만, 사실 문제 조건에서는 그럴 필요가 없다
무슨 의미냐면, 왼쪽을 어떻게 거쳐왔고 몇개의 간선을 거쳐왔건 알 바 없다는 소리다
몰라도 괜찮다
그냥 왼쪽이 오른쪽보다 6 가중치가 모자라는구나
그럼 누적 가중치를 6만큼 왼쪽에 더 주면 오른쪽과 똑같아지겠구나
가 결론이다
C에서 D로 가는 간선을 1만큼 늘리고, E에서 D로 오는 간선은 2만큼 늘려야 E에 물려있는데 5개의 노드가 같아지고
이런거 알필요 없다는 소리다 (구하란 소리 없으니까)
그렇기 때문에 그냥 누적 가중치를 DP로 계속 갱신하며, 트리 구조의 클래스도 필요없이 DFS만 포화이진트리 구조에 맞게 계속 DFS로 타고 내려가는 것이다
* */