문제 url :

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

목표:

• 특정수를 제곱수의 합으로 표현했을 때에 그 항의 최소개수를 구하라

조건:

• 1 ≤ N ≤ 100,000
• O(N**2)이하로 O(N) 혹은 O(NlogN)이어야 한다.

solution 설명 :

main idea는 d[i]가 되기전에 어떤 제곱수의 최소항의 개수가 d[i]로 채택이 되었느냐를 구하는 것이다.

• D의 index i는 i를 구성하는 제곱수 의 최소 개수를 넣는 것이다.
• 일단 D[i]를 순서대로 하나씩 돈다.
  • j를 i의 루트 2까지 돌린다.
  • i 보다 작은 j의 제곱수를 빼서 D[i]가 되기 전에 온 값의 최소항 수에 +1한 값들을 구한다.
  • 그것들 중 가장 작은 값을 구해서 채운다.

import sys
n = int(sys.stdin.readline())
D = [0]*(n + 1)
for i in range(1, n + 1):
  D[i] = min([D[i - j*j] + 1 for j in range(1, int(i**0.5) + 1)])
print(D[n])