문제

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

문제 풀이

• 파이썬은 제한시간이 1.5초지만 기본 문제의 제한시간은 0.15초인 것을 보고 고려해서 코딩을 했다.
• bfs를 사용하여 가장 짧은 횟수로 1로 만드는 방법을 구현
• 이때 방문한 숫자는 다시 연산하지 않도록 visits배열 선언

코드

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

dq = deque()

ans=0
visits = [0]*((10**6)+1)

dq.append([n, 0])

while dq:
    val, cnt = dq.popleft()
    if val==1:
        ans=cnt
        break

    if visits[val]==0:
        visits[val]=1
        if val%3==0:
            dq.append([val//3, cnt+1])
        if val%2==0:
            dq.append([val//2, cnt+1])
        dq.append([val-1, cnt+1])
print(ans)

후기

1년전만 해도 헉헉 거리면서 못 풀었던 문제인데 지금은 5분만에 푼 것을 보고 열심히 하면 안되는건 없다고 느낌