bright

# 시간 초과 

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])

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

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

# 틀린 코드.. 왜? 

n, k = map(int,input().split()) # n 개의 동전, k 원 

coin = [0]*n 

for i in range(n):
  coin[i] = int(input())

dp = [10001]*(k+1)
dp[0] = 1

for i in coin : 
  for j in range(i, k+1):
    if dp[j-i] != 10001 :

      if dp[j] == 10001 : 
        dp[j]= 0
      dp[j] += dp[j-i]

print(dp[k])

# 정답

n, k = map(int,input().split()) # n 개의 동전, k 원 

coin = [0]*n 

for i in range(n):
  coin[i] = int(input())

dp = [0]*(k+1)
dp[0]=1

for i in coin :
  for j in range(i, k+1):
    if j-i >= 0 : 
    # j-i 를 만드는 방법에 지금 coin 값을 더하는 식을 세울 수 있으므로. 
      dp[j] += dp[j-i]

print(dp[k])

n = int(input()) # 오르막 수 <= 1000

dp = [ [0,0,0,0,0,0,0,0,0,0] for _ in range(n)] 

for i in range(10):
  dp[0][i] = 1

for i in range(1,n):
  for j in range(10):
    for k in range(j+1):
      dp[i][j] += dp[i-1][k]
      
print( sum(dp[n-1])%10007 )

t = int(input())

n = [0]*t
m = [0]*t 
for i in range(t):
  n[i],m[i] =  map(int,input().split())

for i in range(t):
  dp = [0]* n[i]
  dp[0] = m[i]

  for j in range(1,n[i]): 
    dp[j] = dp[j-1]*(m[i]-j)//(j+1)

  print(dp[n[i]-1])

n = int(input())  # 사려는 카드의 개수 
data = [0]+list(map(int,input().split()))

# n 개를 사기 위해 가장 돈을 많이 내는 경우의 수.. 

dp = [0]*(n+1) 

dp[1] = data[1]

for i in range(2,n+1):
  for j in range(1,i+1):
    if dp[i] < dp[i-j] + data[j]:
      dp[i] = dp[i-j]+ data[j]
print(dp[n])