[백준] 1699 : 제곱수의 합

www.acmicpc.net/problem/1699

1699번: 제곱수의 합

---

• 이전 단계의 최솟값들을 저장해놓고 단계별로 구해나간다.
• i 값의 최소 개수를 구하기 위해, 우선 i 보다 작은 제곱값들을 전부 구해놓는다.
• 각각의 제곱값들에 대해서, 이전에 구해놨던 (i - 제곱값) 들 중 최소 개수를 택하고, 제곱값 1개를 더한 값이 최소개수가 된다.
• 비효율적인 코드 같다. 채점시간도 꽤나 걸렸다.
• 배열로 하나하나 저장할 필요 없이 재귀를 통해서도 구할 수 있는 것 같다.

---

import math
n = int(input())
arr = [0, 1, 2, 3] + [0] * (n - 3)
for i in range(1, math.ceil(math.sqrt(n))):     # 제곱수들은 1로 처리
    arr[i ** 2] = 1
for i in range(4, n+1):                                         # 나머지 수에 대해서
    val = math.floor(math.sqrt(i))                              # 자신보다 작은 수들 중 모든 제곱값들에 대하여
    arr[i] = 1 + min(arr[i - x**2] for x in range(1, val+1))    # (제곱값을 뺀 값의 최소개수) + 1 이 최솟값이 됨
print(arr[n])