# 1699 제곱수의 합 -

# 시간 초과 

n = int(input()) # 1<=n <= 100,000 

dp =[10001]*(n+1) 

dp[0]=0
sq=[0]*(n+1)

for i in range(1,n+1):
  sq[i] = i**2
  for j in range(i,n+1):
    k = j - sq[i]

    if k >=0 and dp[k] != 10001 : 
      dp[j] = min( dp[j], dp[k]+1 )

print(dp[n])

 

# 시간 초과 2 

n = int(input()) 
dp = [0] * (n+1) 

for i in range(1, n+1): 
  dp[i] = i

  for j in range(1, i): 
    if (j * j) > i: 
      break 
      
    dp[i] = min(dp[i], dp[i - j * j] + 1) 

print( dp[n])

 

 

# min 함수 사용 하지 말고 if 문 적용하기 

n = int(input()) 
dp = [0] * (n+1) 

for i in range(1, n+1): 
  dp[i] = i

  for j in range(1, i): 
    if (j * j) > i: 
      break 
      
    dp[i] = min(dp[i], dp[i - j * j] + 1) 

print( dp[n])

 

.. 뭔가 비슷하게는 푸는 것 같은데 조금씩 어긋나는 기분.. 

좀 더 생각하고 코딩하기..