백준1463: 1로 만들기(Python)

 

ex) 10이라는 수는 10 -> 9 -> 3 ->1 (1을 빼고 3으로 두 번 나눈다) : 연산 횟수는 3

                        10 -> 5 -> 4 -> 2 -> 1  (2로 나누고 1을 빼고  2로 두 번 나눈다): 연산 횟수는 4

 

n = int(input())
d = [0]*(n+1)


for i in range(2,n+1):
    d[i] = d[i-1]+1
    if i %2 == 0: 
        d[i] = min(d[i//2]+1,d[i])
    if i%3 ==0:
        d[i] = min(d[i//3]+1,d[i])
print(d[n])