백준 1464)1로 만들기

접근방법

-바텀 업 방식으로 진행하였다.

 2 ,3 으로 나누어 떨어지는 지 확인 한 후에 이를 -1 을 한 경우와 비교해 더 작은 수를 배열에 넣어주었디.

 

n= int(input())

d= [0] * (n+1)

d[1]=0

for i in range(2,n+1):

    if i%2 ==0 and i%3==0:

        d[i] = min(d[i//2]+1,d[i//3]+1)

    elif i%2 ==0 and i%3 !=0:

        d[i] = d[i//2]+1

    elif i%3 ==0 and i%2 !=0:

        d[i] = d[i//3]+1

    else:

        d[i] = d[i-1]+1

    d[i] = min(d[i-1]+1,d[i])

    print(d[i])

   

       

print(d[n])