파이썬 알고리즘-85 (BOJ 1463) 1로 만들기

코드

n=int(input())
# 횟수를 저장하는 테이블 초기화
dy=[int(1e3)]*(n+1)
# 1은 0번이므로
dy[1]=0
# 2부터 n까지 돌면서 최소 횟수를 dy테이블에 기록하고, 
# dy테이블에 기록해둔 값을 활용해서 n일 때의 최솟값을 찾는다
for i in range(2,n+1):
    if i%3==0:
        dy[i]=min(dy[i],dy[i//3]+1)
    if i%2==0:
        dy[i]=min(dy[i],dy[i//2]+1)
    dy[i]=min(dy[i],dy[i-1]+1)
print(dy[-1])