BOJ - 1699

백준 문제 링크
제곱수의 합

❓접근법

1. 1부터 N까지 숫자를 증가시키면서 항의 개수를 구해보면,
   1 = 1
   2 = 2
   3 = 3
   4 = 1 (4가 안된다.)
   5 = 2
   6 = 3
2. 여기서 1부터 제곱했을 때 N에 가장 가까운 수를 i라고 한다면,
   DP[N] = min(DP[N], DP[N - i ** i] + 1)로 볼 수 있다.
   예를 들어, i가 1, 2일 때
   DP[4] = min(DP[4], DP[4 - 1**1] + 1) = 4
   DP[4] = min(DP[4], DP[4 - 2**2] + 1) = 1 이므로
   i가 2일 때 DP[4]가 가장 최솟값이 된다.
3. 따라서 점화식은
   DP[N] = min(DP[N], DP[N - i ** i] + 1)

👌🏻코드

import math
N = int(input())

DP = [0] * (N+1)

for i in range(1, N+1):
    DP[i] = i
    
    for j in range(1, int(math.sqrt(i)) + 1):
        DP[i] = min(DP[i], DP[i - j * j] + 1)
        
print(DP[N])

너무 어려웠음 ;;; ;