[C++][백준 17626] Four Squares

https://www.acmicpc.net/problem/17626

 

풀이

dp(제곱수의 개수)로 풀이했을 때, dp[i - 1]의 값에 +1을 하거나, 어떤 dp 값에 제곱수를 하나 더하는dp[x] + 1 중 가장 작은 값을 선택해 나가는 식으로 진행하면 된다

만약 13의 제곱수의 개수를 구해야 한다고 했을 때, 제곱수로 13을 만들 수 있는 경우의 수는

3^2 + 1 + 1 + 1로 표현되는 12에 +1 하거나

또는 3^2으로 표현되는 9에 +2^2 또는 2^2로 표현되는 4에 +3^2 하는 식으로 제곱수를 하나 더함으로써 만들 수 있다

따라서 가능한 경우 중 가장 작은 값을 골라주면 된다

 

제출 코드

#include <iostream>
using namespace std;
int dp[50001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        dp[i] = dp[i - 1] + 1;
        for (int j = 2; j * j <= i; j++)
            dp[i] = min(dp[i], dp[i - j * j] + 1);
    }
    cout << dp[n];
}