[트리] 백준 2263번: 트리의 순회 / 골드 3

https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

www.acmicpc.net

import sys
sys.setrecursionlimit(10**5)
n = int(input())
inord = list(map(int, sys.stdin.readline().split()))
postord = list(map(int,sys.stdin.readline().split()))

dct = {}
for i in range(len(inord)):
    dct[inord[i]] = i

def divide_and_conquer(in_start, in_end, post_start, post_end):
    if in_end < in_start:
        return

    node = postord[post_end]
    print(node, end=" ")
    i = dct[node]
    left = i - in_start

    divide_and_conquer(in_start, i-1, post_start, post_start + left-1)
    divide_and_conquer(i+1, in_end, post_start + left, post_end-1)

divide_and_conquer(0, n-1, 0, n-1)

분할 정복으로 풀 수 있는 문제다.

아이디어가 떠올랐으면 구현만 잘 하면 되는데

이상하게 계속 런타임에러가 떠서 봤더니

최대 재귀횟수를 10**9로 하면 에러가 뜨고 10**5로 하면 통과가 됐다.. ???