[Dynamic Programming][Medium] 279. Perfect Squares

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

 

 

Q. 정수 n 이 주어질 때, perfect square numbers의 합으로 이 정수를 만든다. 

 이때 최소의 이 perfect square numbers의 수를 구하라. 

 

 

Solution. 

 

 합이 n 이 되어야 하므로, 합이 n 보다 커지는 순간 진행을 멈춘다. 

 합이 n 이 되면 여지껏 더한 과정의 합계를 구하고, 

 그 과정의 합계 중, 가장 작은 값을 찾는다. 

 

 합은 1부터 n 사이의 값 중, 제곱수로만으로 구성하며, 

 최적화를 위해 n 보다 이 값이 커지는 순간 바로 loop를 탈출한다. 

 

 로직으로 코드를 작성해 본다. 

 

  

int numSquaresdp(int n, vector<int>& vCache)
{
    if (n == 0)	return 0;

    int idx = n - 1;
    if (vCache[idx] >= 0)
        return vCache[idx];

    int minV = INT_MAX;
    for (int q = 1; q <= n ; ++q)
    {
        int cur = n - (q*q);
        if (cur < 0)	break;
        minV = min(minV, 1 + numSquaresdp(cur, vCache));
    }
    return vCache[idx] = minV;
}

int numSquares(int n) 
{
    vector<int> vCache;
    vCache.resize(n, -1);
    return numSquaresdp(n, vCache);
}

 

 

최상의 결과를 얻지는 못했지만, 

적당한 결과를 얻었다. 

 

다음 기회에 추가 최적화를 해 본다.