[백준] 1463 - 1로 만들기 Python

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

import sys

input = sys.stdin.readline

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

for i in range(2, N + 1):
    if i == 2 or i == 3:
        dp[i] = 1
    dp[i] = dp[i - 1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i // 3] + 1, dp[i])
    if i % 2 == 0:
        dp[i] = min(dp[i // 2] + 1, dp[i])

print(dp[-1])