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

문제링크 : https://www.acmicpc.net/problem/13325

13325번: 이진 트리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int k, tsize, result;
int arr[1<<21];

int func(int node)
{
    if(node*2>=tsize) //리프노드
    {
        result+=arr[node];
        return arr[node];
    }
    else
    {
        int l = func(node*2); //왼쪽
        int r = func(node*2+1); //오른쪽
        result+=abs(l-r) + arr[node]; //갭 + 현재노드
        return arr[node] + max(l, r); //현재 노드 + 큰 값
    } 
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> k;
    tsize = 1 <<(k+1);
    for(int i=2; i<tsize; i++) cin >> arr[i]; //1은 루트노드
    func(1);
    cout << result;
    return 0;
}

 

상당한 헷갈림을 느끼고 다소 검색을 통해 풀 수 있었던 문제이다.

이진트리이며, k의 크기가 1~20이므로 배열의 크기를 1<21로 설정한다.

이후 트리의 사이즈에 사용할 tszie는 1<<(k+1)인데 이는 루트를 감안해서이다.

따라서 입력 반복문도 루트를 제외한 i=2부터 입력을 받는다.

 

이후 재귀문을 통해 탐색을 시작한다.

입력받은 값 기준으로 해당 값의 자식인 왼쪽 (node*2) 오른쪽 (node*2+1)을 탐색한다.

해당 왼쪽의 값과 오른쪽의 값의 차이가 왼쪽 오른쪽을 같게 만들어야 어느 한쪽에 더해줘야하는 값이 된다.

위 계산은 왼쪽 오른쪽 값의 부모 노드 일때 진행된다.

현 부모노드도 더해줘야 하는 값이기에 위 계산을 통해 구한 차이값을 더해줄때 현 노드의 값도 같이 더해준다.

 

부모로 거슬러 올라갈수록 재귀를 반복하게 되는데, 이때 현 노드의 값과 자식 노드 중 큰 값을 반환해준다.

이렇게 반환된 값을 기준으로 다시 차이값을 계산하게 된다.

 

현 노드가 리프노드일때는 위 계산을 할 필요가 없다.

각 리프노드에 대해서는 부모노드일때 필요한 계산을 통해 이미 차이값을 구해서 더해줬기 때문에 현 리프노드의 값들만 더해주면 된다.

 

<예제>
3
1 2 1 3 2 4 1 1 1 1 1 1 1 1


     1         2
   1   3     2   4
  1 1 1 1   1 1 1 1
  
-> 재귀로 인해 밑부터 계산
왼쪽 2쌍부터 차례로 계산

11 -> 갭 x : return 1+1 = 2
11 -> 갭 x : return 1+3 = 4

24 -> 갭 2 : return 1+4 = 5

----------------------------

11 -> 갭 x : return 1+2 = 3
11 -> 갭 x : return 1+4 = 5

35 -> 갭 2 : return 2+5 = 7

----------------------------

57 -> 갭 2 : return 0+7 = 7 (루트)

각 노드의 합 : 21
갭의 합 : 6
총합 : 27