[백준] 무한이진트리(python)

백준, 무한이진트리

2078번: 무한이진트리

TL;DR

• 트리(Tree)
• 수학(Mathematics)

문제 요약

1. 규칙에 의해 생성되는 무한 이진 트리에서 입력으로 받은 지점에 도착하기 까지 왼쪽 이동 횟수와 오른쪽 이동 횟수를 각각 구하는 프로그램을 작성하는 문제이다.
2. 규칙은 다음과 같다.
    1. 루트에는 (1, 1)이 할당된다.
    2. 어떤 노드 (a, b)가 할당되었을 때, 해당 노드의 왼쪽 자식은 (a + b, b)가 되고, 오른쪽 자식은 (a, a + b)가 할당된다.
3. 잘못된 입력은 주어지지 않는다고 가정한다.

 

- 이진 트리에서 노드에 도착하기까지 이동한 왼쪽 이동 횟수와 오른쪽 이동 횟수를 구하면 되는 문제이다.

- 트리를 작성하는 규칙에서 문제의 해결 방법을 유추할 수 있어야 한다.

입출력 형태

[그림 1] 입출력 예시

 

[그림 1]에서 확인할 수 있는 예시에 따르면 (3, 4)인 노드에 방문하기 위해서는 왼쪽으로 2번, 오른쪽으로 1번 이동해야 한다고 되어 있다. 이를 확인하기 위해서는 문제에서 주어진 트리 구성 규칙에 따라서 트리를 직접 그려보면 이해에 도움이 된다.

 

[그림 2] 규칙에 따라 그린 예시

 

[그림 2]는 문제에서 주어진 규칙에 따라 입력받은 노드인 (3, 4)까지 그림으로 그린 것이다. 이와 같이 트리가 입력 노드까지 무한히 생성된다. 트리에서 얻을 수 있는 규칙을 찾아서 문제를 해결해야 한다.

풀이

첫 번째로 생각한 방법은 단순히 주어진 규칙에 따라 방문을 원하는 노드까지 트리를 생성한 후 부모 노드로 따라 올라가며 문제를 해결하는 방법을 생각하였다.

import sys
from collections import defaultdict
INPUT = sys.stdin.readline

A, B = map(int, INPUT().split())
tree = [(0, 0), (1, 1)]
i = 1
L, R = 0, 0
# (A, B)가 나올 때까지 트리 구성
while True:
  sub_tree = []
  x, y = tree[i]
  if x + y == A and y == B:
    tree.append((x + y, y))
    break
  if x == A and x + y == B:
    tree.append((x, x + y))
    break
  sub_tree.append((x + y, y))
  sub_tree.append((x, x + y))
  tree += sub_tree
  i += 1

index = tree.index((A, B))
while index != 1:
  if index % 2 != 0:
    R += 1
  else:
    L += 1
  index = index // 2
print(L, R)

각 노드에 대한 서브트리를 만들며 규칙에 따라 트리를 구성한다. 완전 이진 트리이기 때문에 1차원 배열로 표현할 수 있으며 다음과 같은 성질을 갖는다.

1. i번째 인덱스의 부모 노드는 i / 2를 버림한 값이다.
2. i번째 인덱스의 왼쪽 자식 노드의 인덱스는 2 * i이다.
3. i번째 인덱스의 오른쪽 자식 노드의 인덱스는 2 * i + 1이다.

이 성질을 이용하여 방문한 노드 i에서 부모 노드를 찾아 올라가며 왼쪽과 오른쪽 이동거리를 찾아서 문제를 해결하는 방법을 구현하였다. 하지만 이 방법의 경우 A와 B의 값의 상한이 2,000,000,000으로 매우 큰데 비해 메모리 제한은 128MB로 걸려있기 때문에 A와 B의 값이 커질 경우 메모리 초과가 발생할 수 있다.(실제로 발생하였다.)

다른 풀이

직접 트리를 만드는 방식으로는 문제를 해결하기 어렵고, 다른 방법을 찾아야 한다. 다른 방법은 수학적으로 접근하는 방법이 있다. 이 풀이의 경우 내가 직접 생각해내지는 못했고, 참고에 있는 블로그분의 풀이를 참고하여 문제를 해결하였다.

문제에 트리 규칙을 잘 살펴보면 이 규칙이 있다. "왼쪽 자식 노드는 (a + b, b), 오른쪽 자식 노드는 (a, a + b)를 할당한다." 이 규칙에 따르면 노드의 A값이 더 큰 경우는 왼쪽으로 이동한 경우이고 그 반대의 경우는 오른쪽으로 이동한 경우가 된다. 이 성질을 이용해서 문제를 해결할 수 있다.

import sys
INPUT = sys.stdin.readline

A, B = map(int, INPUT().split())
L = R = 0

while A > 1 and B > 1:
  if A > B:
    L += A // B
    A %= B
  else:
    R += B // A
    B %= A
L += A - 1
R += B - 1
print(L, R)

 

이 방법이 규칙을 이용한 풀이이다. A가 B보다 큰 경우는 왼쪽으로 이동한 경우이므로 L을 증가시키고 A의 값을 부모 노드의 값으로 갱신한다. 이 갱신이 B로 나눈 나머지가 되는 이유는 A와 B의 합으로 이루어져있기 때문에 B로 나눈 나머지를 통해 부모 노드의 값을 얻어낼 수 있기 때문이다. 반대의 경우는 오른쪽 이동 거리 R을 증가시킨다.

 

while문이 실행되고 난 이후에는 A 또는 B는 1의 값이 할당되게 된다. 그 경우는 루트 노드와의 거리를 측정해주면 된다. 이렇게 구하고 나면 원하는 답을 얻을 수 있다.

참고

이 코드는 수학적으로 해석하지 않고 단순 메모리를 할당한 나의 풀이 방법으로는 메모리 초과가 발생하기 때문에 아래 블로그분께서 작성하신 방법을 참고하여 내용을 이해한 후 문제를 풀었다. 감사의 말씀을 전한다.

[백준]무한이진트리(2078)