백준 #14570 나무 위의 구슬

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(node, k):
    left = graph[node][0]
    right = graph[node][1]
    if left == -1 and right == -1:
        print(node)
        exit()
    elif left != -1 and right == -1:
        dfs(left, k)
    elif left == -1 and right != -1:
        dfs(right, k)
    else:
        if k % 2 == 1:
            dfs(left, int(k - k // 2))
        else:
            dfs(right, int(k - k // 2))


n = int(input())
graph = [[-1, -1] for _ in range(n + 1)]
for i in range(1, n + 1):
    left, right = map(int, input().split())
    graph[i][0] = left
    graph[i][1] = right


k = int(input())
dfs(1, k)

풀이

구슬 하나하나를 떨어뜨리면서 풀었었는데 시간초과와 메모리초과 때문에 통과를 못했다 ㅠㅠ

결국 구글의 힘을 빌려 풀었다!!

만약 현재 노드의 자식이 없는 경우 현재 노드를 출력해주고 종료시켜준다

왼쪽자식만 있거나 오른쪽자식만 있는 경우에는 해당 방향으로 구슬을 보내준다

문제는 양쪽 자식 둘다 있는 경우인데, 왼쪽 서브 트리 구슬 개수 <= 오른쪽 서브트리 구슬 개수이면 왼쪽으로 보내기때문에 현재 구슬 k 개가 홀수인 경우에는 k의 절반을 뺀 나머지 부분을 왼쪽으로 보내주고 k가 짝수일 경우에는 k의 절반을 뺀 나머지 부분을 오른쪽으로 보내준다.

이유는 예를들어 4개의 구슬을 떨어뜨린다면 왼 오 왼 오 이렇게 갈 것이기 때문에 짝수인 경우에는 오른쪽, 홀수인 경우에는 왼쪽으로 보내주면 된다!