백준 17626. Four Squares

https://www.acmicpc.net/problem/17626

17626번: Four Squares

 

dp[i] : i를 넷 이하의 제곱수의 합으로 표현한 제곱수의 합 중 최소 갯수로 합한 갯수. 

 

우선 자연수 1,2,3은 각각 

1 = 1^2 

2 = 1^2 + 1^2 

3 = 1^2 + 1^2 + 1^2 로만 표현할수 있다.

 

4는 1^2 + 1^2 + 1^2 + 1^2 와 2^2로 표현 할수 있고 작은 갯수는 2^2이다.

 i의 제곱수에 포함될수 있는 값은 1부터 sqrt(i)까지이므로

dp[i]는 dp[1]부터 dp[sqrt(i)]까지의 값중 제일 작은 값 + 1이다.

그런데 제곱근이 정수라면 그 수 자체만으로 i가 되므로 dp[i] = 1로 해주면 된다.