제곱수의 합

문제

숫자 N을 제곱수의 합으로 표현하고자 할 때, 사용해야 하는 제곱 수의 최소 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 숫자 45를 제곱수의 합으로 표현하고자 할 때 필요한 제곱 수의 최소 개수는 2개이며, 이는 다음과 같다.

45 = 3^2 + 6^2

 

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 )  

출력

필요한 제곱 수의 최소 개수를 출력한다.

 

예제 입력

45

예제 출력

2

 

예제 입력

38

 

# 풀이

우선 문제의 규칙은 이렇다

dp[0] = 0

dp[1] = 1^1
dp[2] = 1^1 + 1^1
dp[3] = 1^1 + 1^1 + 1^1
dp[4] = 1^1 + 1^1 + 1^1 + 1^1 or 2^2
…
dp[7] = 2^2 + 1^1 + 1^1 + 1^1
dp[8] = 2^2 + 2^1
dp[9] = 3^2
dp[10] = 3^2 + 1^1

 

여기서 dp[4]인 경우를 보자

dp[4] = dp[3]+1 = dp[4 - 1*1]+1 과 같다고 볼 수 있다.

dp[4] = dp[4 - 2*2] + 1

 

여기서 dp[4] = dp[4 - 3*3] + 1 은 될 수가 없다 이미 4를 초과해버렸으니...

 

dp[16] = dp[16 - 1*1] + 1

dp[16] = dp[16 - 2*2] + 1

dp[16] = dp[16 - 3*3] + 1

dp[16] = dp[16 - 4*4] + 1

 

즉 점화식을 도출해보자면

dp[i] = dp[i - x*x] + 1

이 나온다.

 

#코드

import sys
import math
 
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  n        = int(input()) 
  dp_table = [0]*(n+1)
  nSqrt    = int(math.sqrt(n))  
  
  if n == nSqrt**2: 
    dp_table[n]=1
  else:
    for i in range(1, n+1): 
      for j in range(1, int(math.sqrt(i))+1): 
        if i == j*j:
          dp_table[i] = 1
        if dp_table[i]>0:
          dp_table[i] = min(dp_table[i], dp_table[i-j*j]+1)
        else:
          dp_table[i] = dp_table[i-j*j]+1
          
   
  print(dp_table[n])