백준 1463 파이썬 python : 1로 만들기 @@황소처럼 우직하게@@자 가자~

다이나믹부터 푸는가?

bfs 부터 풀고 다이나믹을 풀어라 당장.

from collections import deque
n = int(input())

dp = [-1 for i in range(1000001)]

def bfs(v):
    global dp
    q = deque()
    q.append(v)
    dp[v] = 0
    while q:
        now = q.popleft()
        if now == 1:
          return
        if now % 3 == 0 and dp[now // 3] == -1:
            dp[now // 3] = dp[now] + 1
            q.append(now // 3)
        if now % 2 == 0 and dp[now // 2] == -1:
            dp[now // 2] = dp[now] + 1
            q.append(now // 2)
        if now - 1 >= 0 and dp[now - 1] == -1:
            dp[now - 1] = dp[now] + 1
            q.append(now - 1)
bfs(n)
print(dp[1])