1699-平方和

5686 ワード
baekjoon DP plzrun テキストリンク

📚 1699-平方和


平方和
 
問題を理解する
  • この問題では、nより小さい二乗の最値に基づいてソースを作成しようとしたが、
    • 12の場合、9と3:4、8、4:3です.
    ➡️ dp[12] = 3
  • ビットの例に示すように、反例がある.
    • 文を
  • 2nに繰り返し、1 ~ nの間の平方数を検索してチェックします.△ソースコードからすれば、分かりやすいはずです.
    •  
    私のソース
    n = int(input())

dp = []

for idx in range(n + 1):
    dp.append(idx)

for i in range(2, n+ 1):
    for j in range(2, i+1):
        if j * j > i:
            break
        else:
            dp[i] = min(dp[i], dp[i - j * j] + 1)

print(dp[n])
     
    リファレンスソース
    # 참고하여 수정한 코드

n = int(input())

dp = [0] * (n + 1)

for i in range(1, n+ 1):
    dp[i] = i
    j = 1

    while j * j <= i:
        dp[i] = min(dp[i], dp[i - j * j] + 1)
        j += 1

print(dp[n])
     
    時間の複雑さ
    LoginContainer
    jQuery.browserの実現方式