[BOJ]1699平方和
📃 平方和
これはdp値を1からnに更新する方法である.すなわち,小さい頃から取り組んできた典型的なDP問題である.
iからnに回転し、jの1からi-1までの数の二乗値はiより大きくないべきである.
コード#コード#
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より大きくないべきである.
Reference
この問題について([BOJ]1699平方和), 我々は、より多くの情報をここで見つけました https://velog.io/@zioo/BOJ1699제곱수의-합テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol