링크 https://www.acmicpc.net/problem/17626 난이도(solved.ac 참고) 실버5 풀이 input값 n을 받았을 때, 우선 9행에서 이 수가 특정 수의 제곱수인지 여부를 걸러낸다. 처음에는 무조건 그 수와 가장 가까운 제곱수를 찾아내 그 수를 더하고 남은 값을 DP 처리하는, 그리디 방식으로 생각했다. 근데 그렇게 하자니, 12라는 훌륭한 반례가 있다. 12 = 3^2 + 1^2 + 1^2 + 1^2 (총 4개) = 2^2 + 2^2 + 2^2 (총 3개) 그 수와 가장 가까운 제곱수를 항상 더하는 방식으로 가져간다면 위의 12처럼 12와 가장 가까운 제곱수인 3을 가져갔을 때의 개수가 2를 세 개 가져갔을 때의 개수보다 더 많다. 그렇기 때문에 그리디와 같은 방식으로 풀면..