문제

image.png

풀이

먼저, 점화식을 정의하면 아래와 같다.

dp[n] = n 제곱수의 최소항 개수

1 = 1^2
2 = 1^2 + 1^2
3 = 1^2 + 1^2 + 1^2
4 = 2^2
5 = 2^2 + 1^2
6 = 2^2 + 1^2 + 1^2
7 = 2^2 + 1^2 + 1^2 + 1^2
8 = 2^2 + 2^2
9 = 3^2
10 = 3^2 + 1^2
11 = 3^2 + 1^2 + 1^2
12 = 3^2 + 1^2 + 1^2 + 1^2
13 = 3^2 + 2^2

가장 마지막에 ,i^2 왔으면 그 앞부분 까지의 합은 n - i^2이 된다. n-i^2의 제곱수로 표현할때 그 합이 최소인 개수에 i^2항 한개가 추가된 것 이다.

dp[i] = min(dp[i-n^2]) + 1

dp[i] = i로 초기화 하는 이유는, 항의 개수가 최대가 되는 경우는 모두 1^2으로 사용하는 경우가 항의 개수가 최대이기 때문이다. (최소값 찾기 문제 이므로 0으로 초기화시 항상 0이 최소값이 된다.)


#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[100001];
int main() {

    int n;
    scanf("%d",&n);

    for(int i = 0; i <= n; i++) {
        dp[i] = i;
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 2; j*j <= i; j++) {
            dp[i] = min(dp[i],dp[i-j*j] + 1);
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}