[白俊]制作1463号-1

4082 ワード
白駿 DP テキストリンク

📩 ソース


質問する


整数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])
    白駿Baekjoon 2857号FBI-JAVA
    Java oop 20を含む