[C++] 리트코드 279. Perfect Squares

class Solution 
{
public:
    int numSquares(int n) 
    {
        vector<int> dp(n+1, n+1);
        vector<int> dpNum;

        int sum = 1;
        dp[sum] = 1;
        dpNum.push_back(sum);

        for(int i = 3; i < n+1; i+=2)
        {
            sum += i;
            if(sum <= n)
            {
                dp[sum] = 1;
                dpNum.push_back(sum);
            }
            else
            {
                break;
            }
        }

        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < dpNum.size(); j++)
            {
                int sumNum = i + dpNum[j];
                
                if(sumNum <= n)
                {
                    dp[sumNum] = min(dp[sumNum], dp[i] + dp[dpNum[j]]);
                }
            }
        }

        return dp[n];
    }
};

 

풀이

1. 완전제곱수를 저장한다.

2. dp1~12를 순회하면서 i + 완전제곱수가 가능한지 확인하고 해당 dp에 있는 count와 비교해서 작은 값을 넣어준다.

 

느낀점

DP문제의 특성을 더 파악해야 될 것 같다.

 

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