[백준] 1699번

💻 C++ 기반

제곱수의 합
https://www.acmicpc.net/problem/1699

✔️ 반례: N이 43일 때

1. 테이블 정의하기
먼저 과정을 직접 생각해보자.
N = 1일 때: 1^2
N = 2일 때: 1^2 + 1^2
N = 3일 때: 1^2 + 1^2 + 1^2
N = 4일 때: 2^2
﹒
﹒
﹒

💡 N이 제곱수인 것과 제곱수가 아닌 것의 차이가 약간 보인다!
(N이 제곱수면 답이 늘 1이 나오고, 그게 아니면 N에서 N보다 작은 제곱수를 빼고 나서 계산하면 된다)

dp[i] : i의 제곱수 항의 최소 개수


2. 점화식 찾기
dp[i] = dp[sqrt(i) * sqrt(i)] + dp[i - sqrt(i) * sqrt(i)]

⚠️ N = 43일 때를 생각해보자
43
= 6^2 + 2^2 + 1^2 + 1^2 + 1^2
= 5^2 + 3^2 + 3^2
﹒
﹒
﹒
우리가 세운 점화식의 논리대로라면 dp[43]의 값이 5가 나와버린다.
그럼 어떻게 해야 할까?

💡 sqrt(i)부터 1까지 위의 점화식을 계속 계산하며 min 값을 갱신해주면 된다!


3. 초기값 정하기
dp[N보다 작거나 같은 제곱수] = 1

#include <cstdio>
#include <cmath>
#include <algorithm>

#define MAX_N 100001

using namespace std;

int dp[MAX_N];

int main()
{
    int N;
    scanf("%d", &N);

    int num = 1;
    while (num * num <= N)
    {
        dp[num * num] = 1;
        num++;
    }

    for (int i = 2; i <= N; i++)
    {
        int temp = sqrt(double(i));
        dp[i] = dp[temp * temp] + dp[i - temp * temp];
        for (int j = temp - 1; j > 0; j--)
        {
            dp[i] = min(dp[i], dp[j * j] + dp[i - j * j]);
        }
    }

    printf("%d", dp[N]);
    return 0;
}