[DP] Perfect Squares

perfect squeres는 결국 제곱수를 말하는데 가장 적게 쪼갤 수 있는 제곱수 경우의 수를 구하라는 문제이다

예컨데 13이라면 4와 9라는 제곱수를 더한 꼴이 가장 적은 경우의 수일 것이다.

 

전형적인 dp문제이다

dp라는 배열을 n까지 만든다

이때 초깃값으로 dp[0]은 0일 것이다.

dp[ i ]는 i라는 수에 대한 minmum squre일 것이다.

따라서 이전 제곱수를 빼가면서 각 element의 해를 구하면 된다.

예를 들어 dp[13]은 기존 13의 값과 dp[13-1], dp[13-4]. dp[13-9] 를 비교하면 된다.

이 비교값중 가장 작은 값이 dp[13] 이 될 것이다.

주의할 부분은 dp[i]는 이미 만들어진 원소이므로 초깃값이 1이라는 부분이다