[백준] 1463 1로 만들기 Python

[백준] 1463 1로 만들기 Python

처음에는 bfs로 풀면 되지 않을까 싶어서 from collections import deque를 사용해서 풀었다.
하지만, 시간초과가 났다. 아마 문제 조건에 n이 10의 6승이라서 계산하는데 시간이 드는 것 같다.

시간초과

from collections import deque
n=int(input())
q=deque()
q.append((n,0))
ans=0
while q:
    x,cnt=q.popleft()
    if x==1:
        ans=cnt
        break

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

    q.append((x - 1, cnt + 1))  # 1을뺀다


print(ans)

개선해서 푸니깐 또 풀렸다.

from collections import deque
n=int(input())
q=deque()
q.append(n)
ans=0
visited=[0 for _ in range(n+1)]
while q:
    x=q.popleft()

    if x==1:
        break

    if x%3==0 and visited[x//3]==0:
        q.append(x//3)
        visited[x//3]=visited[x]+1
    if x%2==0 and visited[x//2]==0:
        q.append(x//2)
        visited[x//2]=visited[x]+1
    if visited[x-1]==0:# 1을뺀다
        q.append(x-1)
        visited[x-1]=visited[x]+1



print(visited[1])

DP

그래서 dp로 풀어봤다.

n=int(input())
dp=[0 for _ in range(1000001)]

for i in range(2,n+1):
    #1빼기
    dp[i]=dp[i-1]+1

    #3으로 나누기
    if i%3==0:
        dp[i]=min(dp[i],dp[i//3]+1)
    if i%2==0:
        dp[i]=min(dp[i],dp[i//2]+1)
print(dp[n])