LeetCode (C/C++) 279. Perfect Squares

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

---

풀이

dp를 이용, 제곱수일 때의 개수를 1로 초기화한다.

현재 숫자에 도달하기 위해서는 이전의 제곱수 값들을 더해야 하므로, 현재 숫자보다 작은 제곱수에 저장된 값들로 최소 수의 합을 구한다

---

코드

class Solution {
public:
    int numSquares(int n) {
        int dp[10001];
        fill(dp, dp + 10001, 10001);

        // 제곱수는 1로 초기화
        int num = 1;
        while (num * num <= n) {
            dp[num * num] = 1;
            num++;
        }
        
        for (int i = 1; i <= n; i++) {
            if (dp[i] != 10001) continue;
            
            // 현재 숫자보다 적은 제곱수에 저장된 값 사용
            for (int j = 1; j * j <= i / 2; j++) {
                dp[i] = min(dp[i], dp[i - j * j] + dp[j * j]);
            }
        }
        return dp[n];
    }
};