BOJ 1463 1로 만들기 Python3

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

1463번: 1로 만들기

 

 

from collections import deque
import sys
input = sys.stdin.readline

X = int(input())

def dfs():
    queue = deque()
    queue.append((X, 0))
    while queue:
        x, cnt = queue.popleft()
        if x == 1:
            print(cnt)
            return

        if (x % 3) == 0:
            queue.append((x//3, cnt+1))

        if (x % 2) == 0:
            queue.append((x//2, cnt+1))

        queue.append((x-1, cnt+1))

dfs()