백준 #1699 <제곱수의 합>

난이도 : 실버2
소요시간 : 48m
사용한 풀이법 : DP

---

풀이 과정

1. dp용 리스트 선언
   1. 각 인덱스에는 1로만 표현했을경우의 개수를 넣는다. 즉, 인덱스 번호를 그대로 대입!
2. 루프를 돌면서 DP탐색 시작
   1. 인덱스 번호보다 작은 제곱 수 중에서 가장 큰 값을 찾는다.
   2. 현재 인덱스 번호에서 해당 제곱 수를 뺀 인덱스 번호에 +1을 한 후, 대소비교를 진행한다.
   3. ex) dp[10] = dp[10-33]+1 = dp[1]+1 (11 + 3*3, 2개!)
   4. +1을 하는 이유는 앞선 dp[]값에 제곱 수의 경우가 하나 추가되는 것이기 때문

작성 코드

import math
N = int(input())
dp = [x for x in range(N+1)]


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