1699:제곱수의 합
https://www.acmicpc.net/problem/1699
틀린 풀이
d[i] = i의 제곱수의 항의 최소 개수
n과 가장 가까운 제곱수를 찾음
d[n-(n과 가장 가까운수의 제곱수)] + 1
+1을 하는 이유
- 제곱수 자체도 하나 이기 때문에
예를 들어
- d[7] = d[ 7 - 2^2 ] + 1 = d[3] + 1 이라고 생각했다
하지만, 위의 예시에서, d[3]이 가장 작은 값이라는 보장이 없다
즉, 가장 가까운 제곱수를 찾는 것이 틀림
맞는 풀이
예를 들어 ,
- d[25] 를 구하려고 할때,
- d[25-1^2] + 1
- d[25-2^2] + 1
- d[25-3^2] + 1
- d[25-4^2] + 1
min 값이 답
