1로 만들기

p. 217

 

방법 1

x=int(input())

d=[0]*30001

# 1일때는 연산횟수가 0임
for i in range(2,x+1):
  # -1을 한 경우
  d[i]=d[i-1]+1

  if i%5==0:
    d[i]=min(d[i],d[i//5]+1)
  if i%3==0:
    d[i]=min(d[i],d[i//3]+1)
  if i%2==0:
    d[i]==min(d[i],d[i//2]+1)

print(d[x])

 

방법 2

n=int(input())

dp=[999]*((n+1)*3)
dp[0]=0
dp[1]=0
nn=0
for i in range(n+1):
  dp[i*3]=min(dp[i]+1, dp[i*3])
  dp[i*2]=min(dp[i]+1, dp[i*2])
  dp[i+1]=min(dp[i]+1, dp[i+1])

print(dp[n])