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

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

풀이과정

시간제한이 0.15초로 짧고 힌트를 보면 뭔가 상향식? 이기 때문에 그리디보다는 효율적인 알고리즘 설계를 위해 다이나믹 프로그래밍(동적계획법)을 사용하라는 것 같다.

동적계획법은 점화식처럼 사용된 값을 재사용해서 중복 계산을 피하는 방법이다.

이코테에 동일한 문제가 있으니 다시 살펴봐도 좋을 것 같다.

1로 만들기 위한 최소 연산 횟수 = 가장 작은값(1로 빼는경우, 2로 나누는 경우, 3으로 나누는 경우) + 1

dp[i]는 최적의 값에서 +1 한 값으로 갱신해준다.
함수의 호출 횟수를 구해야 하기 때문에 +1 을 해준다.

정답

import sys
n = int(sys.stdin.readline())
dp = [0] * (n+1)  # d[1]을 첫번째로 만들어준다.
for i in range(2, n+1):
    dp[i] = dp[i - 1] + 1 # 1로 빼는 경우
    if i % 3 == 0: # 3으로 나누는 경우
        dp[i] = min(dp[i], dp[i//3]+1)
    if i % 2 == 0: # 2로 나누는 경우
        dp[i] = min(dp[i], dp[i//2]+1)
print(dp[n])