[이취코] 1로 만들기 (Python3)

처음에 짠 코드

n = int(input())
count = 0

if n == 1:
    count = 0

if n == 2:
    count = 1
    

if n == 3:
    count = 1

if n == 5:
    count = 1

else:
    while n != 1:
        if n % 5 == 0:
            n /= 5
            count += 1
        elif n % 3 == 0:
            n /= 3
            count += 1
        elif n % 2 == 0:
            n /= 2
            count += 1
        else:
            n -= 1
            count += 1

print(count)

 

DP 를 적용한 코드

n = int(input())
d = [0] * 30001

for i in range(2, n + 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[n])

 

• 점화식을 세우는 것이 어려움..