이것이 코딩테스트다 with 파이썬 - Chp 8. 다이나믹 프로그래밍_2. 1로 만들기

Try1

x = int(input())
result = 0
while x > 1:
    if x % 5 ==0:
        result += 1
        x //= 5
        continue
    elif x % 3 ==0:
        result += 1
        x //= 3
        continue
    elif x % 2 == 0:
        result += 1
        x //= 2
        continue
    else:
        x -= 1
        result += 1
        continue
print(result)

26
-> 5가 나온다. 답은 3이 도출되어야 한다.

• 아마도 26의 경우 -1을 하고 5를 2번 나눠주는 것이 연산횟수의 최솟값임에도 위의 코드에선 %5, %3, %2, -1의 순서로 진행되므로 %2가 적용되는 식으로 흘러가는 것 같다.
• 논리구조는 맞는 것 같으나, 다이나믹 프로그래밍으로(메모이제이션) 풀어서 해결해야 위의 예외가 해결될 것 같다.

도저히 생각이 나지 않아서 예시 답안을 참조하였다.

예시 답안

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