[실버3] 1699번 : 제곱수의 합

🛠 문제

https://www.acmicpc.net/problem/1699

👩🏻‍💻 해결 방법

처음에 짠 코드는 시간초과가 났었다...
다른 사람의 풀이를 참고해 효율적으로 문제를 풀 수 있었다

소스 코드

n = int(input())

dp = [0] * 100001

for i in range(1, n+1):
  dp[i] = i
  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])