[BOJ]1(no.1463)

質問する

整数Xに使用できる演算は3種類あります.
Xを3で割って、3で割った.
Xを2で割り、2で割ります.
1を減算します.
整数Nが与えられると、上記3つの演算を適宜用いて1が作成される.使用演算回数の最大値を出力してください.

入力

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

しゅつりょく

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

🤔 の意見を打診

dp問題は最初は良いケースを区別することが重要だった.

点火式を構想するときは、top-downで考えるのが簡単そうです.

3に分けると必ずしも3に分ける必要はありません.この3つの場合が適用されます.最初は電子で理解していたのでシャベルで...(バカ)

ヶーシング

3

2

、その他の

アレイの定義

dp[i]:整数i時の最小演算回数

🔥 てんかしき dp[i] = min(dp[i//3]+1, dp[i//2]+1, dp[i-1]+1) 論理は多分そうで、そのまま書くことはできません。 また、2または3に分けているか確認する必要があるので、条件文として追加処理が可能です。

📌 説明する

import sys
input = sys.stdin.readline

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

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

print(dp[n])

レビュー

押し出すのは儚いほどだが、点火式の構想にはまだ慣れていない。 難しいですが、結局はよくなります!DPを押し続ける