[C/C++] 백준 #1699 제곱수의 합(동적 계획법)

어떤 수를 제곱수의 합으로 표현할 수 있습니다.  모든 자연수의 1을 해당 수만큼 더하면 되기 때문에 모든 자연수는 가능하다고 할 수 있습니다.

 

예를 들어서 10과 같은 수는 1을 10번 더해도 되겠지만, 9와 1을 더해도 되고, 4+4+1+1 형태도 가능합니다.

 

동적계획법을 단순하게 한다면, 다음과 같이 할 수가 있습니다.  n을 만들 수 있는 제곱항의 수를 $d_n$이라고 한다면, 

 

$$d_0=0$$

$$d_n=min(d_{n-1}+d_1,d_{n-2}+d_2,...,d_{n/2}+d_{(n+1)/2})$$

 

그런데 이렇게 하게 되면, $d_n$을 구하는 알고리즘 효율이 $O(n)$ 형태가 되게 되고 전체적으로는 $O(n^2)$이 됩니다.

그것을 줄이기 위해서 꼼수를 쓴 것은

1) 제곱수는 최대 3번까지만 합할 수 있다.  1을 4번 할 것이라면, 4를 더하면 된다.  $k^2$을 4번 더하면, $(2k{)}^2$을 1번 더하면 제곱수 더하는 항목을 줄일 수 있다.

2) $k^2$ 항목에서의 계산울 위해서 최대 갈 수 있는 항목은 k-1까지 항목들을 제곱합으로 하고, 각각의 항목을 3배한 값이 된다.

1부터 k-1까지의 제곱의 합은 다음과 같이 표현할 수 있습니다.

$$\sum _{s=1}^{k-1}=\frac{k(k-1)(2k-1)}{6}$$

 

square sum

 

그래서 이런 것들을 이용해서 작성한 소스입니다.  오래전에 짤 때와 지금 다시 돌아본 결과 이게 정말 맞나하는 생각이 드는 부분들이 있네요.  여하튼 소스는 참고용으로 봐주시길 바랍니다.

//----------------------------------------------------------------------------------------
//    baekjoon #1699
//        - by Aubrey Choi
//        - created at 2019-09-11
//----------------------------------------------------------------------------------------
#include <stdio.h>

int MIN(int a, int b) { return a<b?a:b; }
int main()
{
    int n, dp[100001];
    scanf("%d",&n);
    for(int i=1;i<=n;i++) dp[i]=100; dp[0]=0;
    for(int i=1;i*i<=n;i++)
    {
        int max=MIN(i*(i-1)*(2*i-1)/2, n-i*i);
        for(int j=max;j>=0;j--)
        {
            for(int k=1;k<4&&k*i*i+j<=n;k++)
            {
                dp[j+k*i*i]=MIN(dp[j+k*i*i], dp[j]+k);
            }
        }
    }
    printf("%d\n", dp[n]);
}