✍ 문제

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

👏 풀이과정

가장 기본적인 dp로 푸는 문제이다. 다운업 방식을 이용해 주었다.
1. 처음 0 부터 시작하여 N 까지 dp배열을 생성해 주었다.
2. dp배열은 N3만큼 갈 수 있으므로 dp = [N3] (N3+1)이렇게 초기화 해주었다.
3. dp[0]은 사용하지 않으므로 고려하지 않았고 1부터 사용하기 때문에 dp[1]을 1로 초기화 해주었다.

import sys

N = int(sys.stdin.readline())

dp = [N*3] * (N*3+1)
dp[1] = 0
for i in range(1,N+1):
    dp[i+1] = min(dp[i]+1,dp[i+1])
    dp[i*3] = min(dp[i*3],dp[i]+1)
    dp[i*2] = min(dp[i*2],dp[i]+1)

print(dp[N])