[白俊]制作1463号-1

📩 ソース

質問する

整数Xに使用できる演算は3種類あります.

Xを3で割って3で割った.

Xを2で割って2で割った.

1を減算します.

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

入力

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

しゅつりょく

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

👉 の意見を打診

2から10までの最小値を書くと、DPでアクセスできることが確認できます.nの立場では、3つの選択権がある.1か3か2を外せ!

を選択した数字には3つの選択肢があります.すなわち,nが何らかの選択でその数字に移動すると,この数字は再び3種類の選択を行い1に移動する.

したがって、dpリストの値をn(インデックス)から1の最小回数に入力すると、入力された情報により、nがnより小さい値を1つ増加するごとに、1の最小回数を容易に見つけることができる.

n = int(input())
dp = [0] * (n + 1)
for i in range(2, n+1):

    # 첫번째 방법 1을 빼줌
    dp[i] = dp[i-1] + 1

    # 3으로 나눌수 있으면 나눠서 최소값 비교
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    # 2로 나눌 수 있으면 나눠서 최소값 비교
    if i % 2 == 0:
        # 6 > 3 > 1로 가는 방법
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[n])