[8/15] 1로 만들기

217 실패

내 코드

...

효율적인 코드

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])

로직

• 낮은 수부터 차례대로 계산해서 최소값을 해당 값으로 저장