[python] 1로 만들기

1. X가 5로 나누어떨어지면 5로 나누기

2. X가 3으로 나누어떨어지면 3으로 나누기

3. X가 2로 나누어떨어지면 2로 나누기

4. X에서 1을 빼기

 

=> 연산을 사용하는 횟수의 최솟값

 

 

x = int(input())

d = [0] * 30001

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