백준 1463(1로 만들기) - Python(파이썬) - 다이나믹

1463번: 1로 만들기

예제 풀이

2-> dp[1]+1,dp[2//2]+1 -> min(1,1)=1

10 -> 3이 나오게 된다.

dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
0	0	(dp[1]+1,dp[2//2]+1) = (1,1) = 1	(dp[2]+1,dp[3//3]+1) = (2,1) = 1	(dp[3]+1,dp[4//2]+1) = (2,2) = 2	(dp[4]+1) = 2	(dp[5]+1,dp[6//2]+1,dp[6//3]+1) = (3,2,2) = 2	dp[6]+1 = 3	(dp[7)+1,dp[8//2]+1) = (4,3) = 3	(dp[8]+1,dp[9//3]+1) = (4,2) = 2	(dp[9]+1,dp[10//2]+1) =(3,3) = 3

💻Python(파이썬)

import sys
n = int(sys.stdin.readline())
dp = [0]*(n+1)
#1인 경우 -> 0
dp[1]=0
for i in range(2,n+1):
    dp[i]=dp[i-1]+1
    if not i%2:
        dp[i] = min(dp[i],dp[i//2]+1)
    if not i%3:
        dp[i]= min(dp[i],dp[i//3]+1)

print(dp[n])