17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 의식의 흐름 dp로 1~n까지 만드는데 필요한 최소 개수 구해보자. + 종이에 1~12까지 구할 수 있는 최소 경우의 수를 써보는데 12 = 3^2+1^2+1^2+1^2(4개) / 2^2+2^2+2^2(3개)로 나뉘는 것을 확인하고 무조건 최대 제곱수를 쓰면 틀리겠구나 생각함 풀이 과정 1. 자연수(n)을 입력받는다. 2. 1~n까지 만드는데 필요한 제곱수의 최소 개수를 구하여 배열(dp)에 저장한다. dp[i] = i를 만드는..
