[백준] 1463. 1로 만들기 | 파이썬

백준 1463. 1로 만들기 - 실버III

문제 설명

---

* 주의 1

2와 3의 최소공배수는 같은 수 때문에 elif 쓰면 안되고 그냥 if문 2개로 처리해야 함!

---

파이썬 코드

N = int(input())
dp = [0] * (N+1)

for i in range(2, N+1):
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[N])