[BOJ]1699平方和


📃 平方和

コード#コード#

import sys
input = sys.stdin.readline 
n = int(input())
dp = [i for i in range(n+1)]

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

print(dp[n])

に答える


これはdp値を1からnに更新する方法である.すなわち,小さい頃から取り組んできた典型的なDP問題である.
iからnに回転し、jの1からi-1までの数の二乗値はiより大きくないべきである.