[Python]동적계획법 백준 1463

   문제

   https://www.acmicpc.net/problem/1463

n번째에서 이전단계는 3개로 나뉜다.

n-1번째의 최솟값 , 2로 나누어 진다면 n//2의 최솟값 , 3으로 나누어 진다면 n//3 의 최솟값

이 셋중  작은것을 골라 1을 더해주게 되면 n번째의 최솟값을 구할수 있다.

n=int(input())
result=[0 for _ in range(n+1)]
 
 
def make_one(n):
    if n==1:
        return
    result[2]=1
    if n==2:
        return
    result[3]=1
    if n==3:
        return
    for i in range(4,n+1):
        result[i] = result[i - 1] + 1
        if i%3==0:
            result[i]=min(result[i//3]+1,result[i])
        if i%2==0:
            result[i]=min(result[i//2]+1,result[i])
 
make_one(n)
print(result[n])