[Algorithm] 백준 13325 이진트리 풀이

이 문제는 다이나믹 프로그래밍으로 분류되어있지만 문제의 이해와 원리를 파악하면 풀 수 있는 문제입니다. 

 

이진포화트리는 Perfect binary tree로 불리며 꽉꽉채워진 이진트리 입니다. 자세한 설명은 다음링크로 남겨놓도록 하겠습니다. 

 

https://yaboong.github.io/data-structures/2018/02/10/1_binary-tree-1/

Binary Tree 종류 - Heap 구현 사전지식

 

---

풀이

저는 weight와 node 두가지 vector를 int형으로 선언해 사용하였습니다. 먼저 weight에 각 edge들의 가중치를 입력받았고 node는 각 edge들의 weight를 더해준 값을 node 변수에 저장하였습니다. 

음의 가중치는 없기 때문에 node를 구하는 과정에서 max값을 쉽게 찾을 수 있을 것입니다. 

이제 문제에서 요구하는 모든 리프까지의 거리가 같게 하면서 에지 가중치들의 총합이 최소를 만족하기 위해 아이디어를 적용해야합니다. 

백준 문제

여기서 핵심 아이디어는 다음과 같습니다. 부모가 같은 자식 노드를 고려할때, max와의 차이가 더 작은 값은 weight를 공통으로 증가시켜야지 에지 가중치들의 총합이 최소가 되도록 하는것입니다.

 

모든 Leaf 노드의 가중치와 max 값의 차이를 구해 node 변수에 저장해놓습니다. (이제 각 node의 값들은 max와의 차이를 구하는데 사용한다) 부모가 같은 자식 노드들만 반복문으로 고려할때, 서로의 차이가 작은 값은 공통으로 가중치를 올려줄 수 있기 때문에 위의 노드에서 고려해주어야 합니다. 그 다음 bottom-up 방법으로 루트노드까지 위의 과정을 반복합니다.

 

---

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;
int main()
{
    
    int k;
    scanf("%d", &k);
    int total_node = pow(2, k+1) -1;
    
    vector <int> weight, node;
    weight.resize(total_node + 3);
    node.resize(total_node + 3);

    for(int i = 1; i < total_node; i++)
    {
        scanf("%d",&weight[i]);
    }
    
    node[0] = node[1] = 0;
    int max = -1;
    
    for(int i = 2; i <= total_node; i++)
    {
        node[i] = weight[i -1] + node[i/2];
        
        if(max < node[i]) // 최대값 찾기.
        {
            max = node[i];
        }
    }

    long long int res = 0;
    
    int last_level = pow(2,k);
    
    for(int i = total_node; i >= last_level; i--)// 초기화 단계라고 생각하면 편함. max와 각 leaf노드들의 가중치의 차이를 저장.
    {
        node[i] = max - node[i];
    }
    
    
    for(int i = total_node - 1; i >= 1; i = i-2)// bottom-up 방식으로 가중치의 합이 최소가 되도록 weight 변수 수정.
    {
        int left = node[i];
        int right = node[i+1];
        int sub = abs(right - left);

        if(left > right)
        {

            weight[i - 1]  = weight[i - 1] + sub;
            node[i/2] = right;
        }
        else if(left < right)
        {
            
            weight[i - 1]  = weight[i - 1] + sub;
            node[i/2] = left;
        }
        else// 같았을 때.
        {
            node[i/2] = left;
        }
    }
    
    
    for(int i = 1; i < total_node; i++)
    {
        res += weight[i];
    }
    
    printf("%lld\n",res);
    
}