質問する

https://www.acmicpc.net/problem/1463
整数Xに使用できる演算は3種類あります.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

整数Nが与えられると、上記3つの演算を適宜用いて1が作成される.使用演算回数の最大値を出力してください.

入力

第1の行は、1以上、106以下の整数Nを与える.

しゅつりょく

1行目の演算回数の最大値を出力します.

アイデア

ダイナミックプログラミングの使用
ex)n=6の場合、dp[6]は最小の場合を求める.
まず、保存先に1を減算した場合.
2に分割し、3に分割する場合は、3に分割する場合に比べて小数を選択します.

1. 1을 빼는 경우
=> dp[5]과 '6에서 1을 뺀 경우'인 1을 더한다
=> dp[6]=dp[5]+1

2. 2로 나누는 경우
=> dp[3]과 '6을 2로 나눈 경우'인 1을 더한다.
=> dp[6]=dp[3]+1

3. 3으로 나누는 경우
=> dp[2]와 '6을 3으로나눈 경우'인 1을 더한다.
=> dp[6]=dp[2]+1

1,2,3を比較し,最小の数字をdp[n]に格納して出力する.

マイコード(Python)

num=int(input())
dp=[0]*(num+1)	#dp[1]부터 사용하므로 num+1로 만들어야 함
for i in range(2,num+1):
    dp[i]=dp[i-1]+1	#1을 뺀 경우를 저장함
    if(i%2==0):
        dp[i]=min(dp[i],dp[i//2]+1)	#2로 나눠지면 비교해서 더 작은 수를 선택
    if(i%3==0):
        dp[i]=min(dp[i],dp[i//3]+1)	#3으로 나눠지면 비교해서 더 작은 수를 선택
print(dp[num])	#마지막 결과 출력

注意:https://www.youtube.com/watch?v=5Lu34WIx2Us&t=2346s