[백준/Python3] 1463 1로 만들기

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

풀이

입력 되는 값이 최대 10^6이 나올 수 있고 짧은 시간내에 풀어야하니 dynamic programming을 이용해 해결하는 문제다. 실제로 dp 표를 만들어 풀면서 점화식을 구하면 쉽게 해결할 수 있다.
N을 1로 만들기 위한 연산 3가지가 나오는데, 이중 어디서 최소값이 나올지 모르므로 해당되는 모든 연산을 실행해봐야 한다.

코드

N = int(input())
dp = [0 for _ in range(10**6 + 1)]
answer = 0

dp[2] = 1
dp[3] = 1

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

answer = dp[N]
print(answer)