백준 13325번 이진 트리

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

이진 트리의 성질만 잘 알고 있다면 재귀함수를 통해 간단히 풀 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 간선의 가중치를 입력 받기 때문에 값이 인덱스 2부터 입력되는 이진트리라고 생각하면 됩니다.

2. 왼쪽 자식 노드로 가는 가중치와 오른쪽 자식 노드로 가는 가중치가 있는데 두 가중치 중 작은 쪽을 큰쪽과 동일하게 바꾼 뒤 둘 다 결과에 더해주면 됩니다.

3. 단말 노드에 도착할 때까지 2번을 진행하고 단말 노드에 도착하면 해당 단말 노드의 가중치만큼 더해주면 됩니다.

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

 

const int MAX = 1 << 21;

 

int N, treeSize;

int result;

int arr[MAX];

 

int DFS(int idx)

{

        if (idx * 2 >= treeSize)

        {

                 result += arr[idx];

                 return arr[idx];

        }

        else

        {

                 int leftNode = DFS(idx * 2);

                 int rightNode = DFS(idx * 2 + 1);

                 result += arr[idx] + abs(leftNode - rightNode);

                 return arr[idx] + max(leftNode, rightNode);

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        treeSize = 1 << (N + 1);

        for (int i = 2; i < treeSize; i++)

                 cin >> arr[i];

 

        DFS(1);

        cout << result << "\n";

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~