#1699 (1) 썸네일형 리스트형 [Baekjoon]1699.제곱수의 합(DP) Baekjoon#1699. 제곱수의 합http://www.acmicpc.net/problem/1699수학적으로 좀 생각을 해봐야하는 문제였다. 어떤 자연수 n을 제곱수의 합으로만 나타낼 때 최소인 경우의 수를 구하는 문제이다. 예시는 문제에도 잘 나와있다. $$11=1^{2}+1^{2}+1^{2}+2^{2}+2^{2}$$ 11은 이렇게 5개의 합으로 나타낼 수도 있지만 이것이 최소인 경우는 아니다. $$11=1^{2}+1^{2}+3^{2}$$ 이처럼 3개의 제곱수의 합으로도 나타낼 수 있으므로 n이 11일때 답은 3 이다. 여기서 한가지 착각을 하기 쉬운데 나도 똑같은 생각을 했다. 제곱수의 합으로 나타낼 때 n보다 작은 가장 큰 제곱수를 사용하여 나타낼 때가 최소일 거라고 생각한것이다. 하지만 그렇지 .. 이전 1 다음
