279. Perfect Squares

279. Perfect Squares

https://leetcode.com/problems/perfect-squares/

문제

풀이

DP표이다.
n = 12일 때를 생각해보자
product는 3까지 이므로 product마다 count를 계산한다.
product 3일 때 9 + 1 + 1 + 1 => 4개이다.
product 2일 때 4 + 4 + 4 => 3개이다.
product 1일 때 1 + .... 1 => 12개이다.
즉 점화식으로 나타내면 다음과 같다.
dp[i] = i // (product product) + dp[i % (product product)]
이것을 코드로 나타내면 다음과 같다.

결과