[백준] 1463번:1로 만들기 (python 파이썬)

문제

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

소스코드

x = int(input())

dp = [0 for _ in range(x+1)]

for i in range(2, x+1):
    dp[i] = dp[i-1]+1
    if i%2 == 0 and dp[i]>dp[i//2]+1:
        dp[i] = dp[i//2]+1
    if i%3 == 0 and dp[i]>dp[i//3]+1:
        dp[i] = dp[i//3]+1

print(dp[x])