[BOJ 13325, Python] Binary Trees

Problem link

boj 13325

Classification

Dynamic programming, Trees, Dynamic programming in trees

Description

If you're like me, you're the kind of person who sticks with a problem for a long time, even if it's not solved right away!

So, along with the problems that I tried but didn't get, there are problems that I tried hard but couldn't solve, along with the competition questions...

To get rid of them, I sometimes read through the questions and chew on them, and I'm so glad I finally found the solution in this post today!

I've had this problem for 8 months now, since my first attempt, and I've tinkered with it a few times since my last attempt, but nothing seemed to work.

def pre_order_detail(graph_dict: dict, target_node: int = 1) -> list:

    result = [target_node]

    if len(graph_dict[target_node]) >= 1:
        for each_element in pre_order_detail(graph_dict, graph_dict[target_node][0]):
            result.append(each_element)
        result.append(target_node)

    if len(graph_dict[target_node]) >= 2:
        for each_element in pre_order_detail(graph_dict, graph_dict[target_node][1]):
            result.append(each_element)
        result.append(target_node)

    return result

My original idea was to use a variation of a potential traversal in the form of a recursive function like the one above, taking a picture of the nodes visited, putting them in a stack-like data structure, and then traversing each trunk.

However, I realized that if I restricted the comparison to trunks from the same parent node, it would be cleaner if I just kept adding the larger of the two values to the parent trunk, and then processed it!

I later solved and categorized this type of problem as a tree DP. I thought it was very similar to DP.

Solving code

# 이진 트리

import sys

input = sys.stdin.readline

tree_height = int(input())
node_number = pow(2, tree_height + 1)

edges = [0] + list(map(int, input().split()))
edge_sum = sum(edges)

now_start = node_number // 2 - 1
now_end = node_number - 1

while now_end:

    for i in range((now_end - now_start) // 2):

        child_edge = now_start + (2 * i)
        next_node = child_edge // 2

        edges[next_node] += max(edges[child_edge], edges[child_edge + 1])
        edge_sum += abs(edges[child_edge] - edges[child_edge + 1])

    now_end = now_start
    now_start = now_start // 2

print(edge_sum)

This is a cleaner code length and time complexity than I initially thought. Now that we have it laid out like this, it's definitely bottom-up.