[C/C++] 17626: Four Squares

일단 bruteforce하게 구현한 코드이다.(굳이 말하면 dp를 조금 이용하여 계산 수를 줄임)

먼저 제곱수는 최소 개수의 제곱수의 합이 1이므로 먼저 dp배열에 저장해준다.

최소개수의 제곱수의 합이 2인 수들은 최소 개수의 제곱수의 합이 1인 수 2개의 합이므로 MakeContinue 함수를 이용해 구하고

최소개수의 제곱수의 합이 3인 수들은 최소 개수의 제곱수의 합이 1인 수와 최소 개수의 제곱수의 합이 2인 수들의 합이므로 이를 이용해서 구하면 된다.

그리고 마지막으로 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으므로 dp[i]==0인 경우에 최소개수의 제곱수의 합이 4인것을 알 수 있다.

 

#include <stdio.h>
#include <string.h>

int dp[100001]; //int tmp=cpy_one[i]+cpy_two[j]; 여기서 dp의 배열의 크기를 넘어갈 수도 있음
int cpy_one[50001];
int cpy_two[50001];

int MakeContinue()
{
    int index1=0,index2=0;
    for(int i=1;i<=50000;i++)
    {      
      if(dp[i]==1)
        cpy_one[++index1]=i;
      if(dp[i]==2)
        cpy_two[++index2]=i;
    }
  return index1+index2;
}
  

int main(void)
  {
    int n;
    scanf("%d",&n);
    dp[1]=1;
    for(int i=1;i<=223;i++) //제곱수
      {
        dp[i*i]=1;
      }
    int index1=MakeContinue();
    for(int i=1;i<=index1;i++)
      {
        for(int j=i;j<=index1;j++)
          {
            if(dp[cpy_one[i]+cpy_one[j]]==0)
              dp[cpy_one[i]+cpy_one[j]]=2;
          }
      }
    
    int index2=MakeContinue()-index1;
    for(int i=1;i<=index1;i++)
      {
        for(int j=1;j<=index2;j++)
          {
            int tmp=cpy_one[i]+cpy_two[j];
            if(dp[tmp]==0)
              dp[tmp]=3;
          }
      }

    for(int i=1;i<=50000;i++)
      {
        if(dp[i]==0)
          dp[i]=4;
      }

    printf("%d",dp[n]);
  }

 

Dynamic Programming을 십분 활용한다면 더 쉽게 구현이 가능하다. 

가장 핵심적인 코드는 밑에와 같다.

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

결국 i보다 작은 수들중에 제곱수를 뺀 수들 중 최소개수의 제곱수의 합이 최소가 되어야한다.

그렇기 위해서 dp[i](현재까지 최소개수의 제곱수)와 1(제곱수를 더함)+dp[i - j * j] (제곱수를 뺀 수의 dp값)를 비교하여 더 작은 수를 찾아내면 된다. 

즉, 여기서는 맨처음 코드처럼 밑에서부터 채운다는 생각이 아니라 위에서부터 채우는 생각이 필요했다. 이때 조심해야할 점은 기저조건을 항상 생각해야한다는 것이고 밑에서부터 채울 때 정확한 점화식으로 채울 수 없고 O(n)으로 풀 수 없다면 위에서부터 어떻게 해야 재귀적으로 풀 수 있는지 생각을 해봐야할 것 같다.

 

이건 조심하자!

배열을 선언하면 항상 그 배열의 max index를 벗어나지 않도록 조심하자!