[baekjoon] 백준 2078번(파이썬): 무한이진트리

문제

2078번: 무한이진트리

알고리즘

- 어떤 노드에서 루트 노드로 이동하는 횟수를 카운트하는 방법으로 문제를 수행했다.

- a와 b가 1보다 클 때까지 반복하여 한쪽의 이동만을 하게끔 만든다.

- 반복이 끝나고 난 후에는 남은 이동 거리를 계산해줘 왼쪽 이동 횟수와 오른쪽 이동 횟수를 출력한다.

코드

import sys

a, b = map(int, sys.stdin.readline().split())
l = 0 # 왼쪽 이동 횟수
r = 0 # 오른쪽 이동 횟수

# a와 b가 1보다 클 때까지 반복한다.
while a > 1 and b > 1:
    # a가 더 크면 왼쪽으로 이동한 경우로
    # a를 b로 나눈 몫은 왼쪽 이동 횟수와 더하고 나머지는 a로 초기화한다.
    if a > b:
        l += a // b
        a %= b

    # 반대로 b가 더 크면 오른쪽으로 이동한 경우로
    # b를 a로 나눈 몫은 오른쪽 이동 횟수와 더하고 나머지는 b로 초기화한다.
    else:
        r += b // a
        b %= a

# a나 b가 1보다 작아지면 남은 이동 거리를 1씩 증가시킨다.
l += a - 1
r += b - 1
print(l, r)

 

실패한 코드(메모리 초과)

import sys
from collections import deque


def bfs():
    l = 0
    r = 0
    queue = deque([[1, 1, r, l]])

    while queue:
        x, y, L, R = queue.popleft()
        # print(x, y, L, R)
        if x == a and y == b:
            return L, R

        nx = x + y
        ny = y + x

        queue.append([nx, y, L + 1, R])
        queue.append([x, ny, L, R + 1])


a, b = map(int, sys.stdin.readline().split())

L_cnt , R_cnt = bfs()
print(L_cnt, R_cnt)

처음에 문제를 풀 때 완전 탐색을 통해 수행했다. 그러나 A와 B의 범위가 매우 크고 메모리 제한이 128MB이기 때문에 메모리 초과가 나온 것을 알 수 있다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법