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

www.acmicpc.net/problem/1463

1463번: 1로 만들기

이 문제는 DP의 가장 대표적인? 예제 같다. 외우듯이 알아두자 

 

# 1463번 1로 만들기
n = int(input())
dp = [0 for _ in range(n+1)]

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

  if i%3 ==0 and  dp[i//3]+1<dp[i]:
    dp[i]=dp[i//3]+1

  if i%2 ==0 and dp[i//2]+1<dp[i]:
    dp[i]=dp[i//2]+1
print(dp[n])