라그랑주의 네 제곱수 정리

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

풀이

• d[i]
  • i 수를 제곱수의 합으로 표현 할 수 있는 경우의 수
• 중복 문제 발생
  • 1
    • 1
    • d[1] = 1
  • 4
    • 1 + 1 + 1 + 1
    • 4
    • d[4] = 2
  • 5
    • 1의 제곱 + 4
      • d[4] = 2
    • 2의 제곱 + 1
      • d[1] = 1
    • d[5] = d[4] + d[1] = 3
    • 여기서 중복 문제가 발생
    • 사실, d[5] = 2
• 중복 해결이 관건