[DP] 하나가 되고 싶어

어떤 정수 X를 1로 만들고자 한다.
사용할 수 있는 연산은 다음과 같은 세 가지 연산이 있다.
1. X가 3의 배수이면 3으로 나누기
2. X가 2의 배수이면 2로 나누기
3. X에서 1을 빼기
양의 정수 N이 주어졌을 때, 위와 같은 세 가지 연산을 사용해서 1을 만들기 위해
사용해야 하는 연산의 최솟값을 출력하시오.
단, 위의 방법으로 1로 만들 수 없는 경우는 존재하지 않는다고 가정해도 된다.

Input
첫째 줄에 양의 정수 N이 주어진다. 1 <= N <= 1,000,000
1

3

17

1000000

Output
첫째 줄에 1로 만들기 위해 사용해야 하는 연산 횟수의 최솟값을 출력한다.
0

1

5

19

import sys
input=sys.stdin.readline

x=int(input()) 
d=[0]*(x+1) 
for i in range(2,x+1):
    d[i]=d[i-1]+1 
    if i%3==0: 
        d[i]=min(d[i],d[i//3]+1)
    if i%2==0: 
        d[i]=min(d[i],d[i//2]+1)
print(d[x])

 

 

 

 

---

연산의 경로와 몇 번 연산했는지 출력하고 싶다면..?

# 연산 경로 & 연산 횟수 출력
n = int(input())

dp = [n+1]*(n+1)
dp[0]=0
dp[1]=0

check = [0]*(n+1)

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

    dp[i] = min(dp[i-1]+1, dp[i])

    if i%3==0 :
        if dp[i]==dp[i//3]+1 :
            check[i]=3
    
    if i%2==0 :
        if dp[i]==dp[i//2]+1 :
            check[i]=2

    if dp[i]==dp[i-1]+1 :
        check[i]=1  

# 연산 경로 출력
print("-------------------------------")
print("연산 경로 출력")
cnt=0
while n!=1 :
    cnt+=1
    print(n, end='->')

    if check[n]==3 :
        n//=3
    elif check[n]==2 :
        n//=2
    elif check[n]==1 :
        n-=1

print(n)
print("연산 횟수: ", cnt)
#print(*dp)
#print(*check)

input
1000000

output
-------------------------------
연산 경로 출력 1000000->500000->250000->125000->62500->31250->15625->15624->7812->3906->1953->651->217->216->108->54->27->9->3->1
연산 횟수: 19