백준 17626번 - Four Squares

# 입력
import sys
n = int(sys.stdin.readline().strip())
squares = [i**2 for i in range(1,int(n**0.5)+1)]
queue = [n]
count = 0

# 처리 - bfs 활용
while len(queue) > 0:
  count += 1
  temp = set()
  for q in queue:
    for s in squares:
      if q < s:
        break
      temp.add(q-s)
  if 0 in queue:
    break
  queue = list(temp)
print(count-1)

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