[백준 17626] Four Squares

www.acmicpc.net/problem/17626

17626번: Four Squares

 

자주 보이는 dp 유형 중 하나 근데 풀 때마다 막막하다...

 

점화식을 세우기 위해 숫자 하나씩 해본다.

1 = 1 * 1

2 = 1 * 1 + 1 * 1

3 = 1 * 1 + 1 * 1 + 1 * 1

4 = 2 * 2

5 = 2 * 2 + 1 * 1

....

10 = 3 * 3 + 1

 

dp[n]은 제곱수 합으로 표현할 때 사용하는 숫자의 최소 개수라고 정의한다.

그러면 n이 제곱이면 dp[n] = 1이다.

n이 제곱이 아니라면 dp[n] = dp[n-i*i] + dp[i*i]이다. 이때 i는 i*i<=n이며 dp[i*i]= 1이므로

dp[n] = dp[n - i*i] + 1 이다.

 

첫 번째 실수:

i를 n에 가장 가까운 수라고 정의함(예를 들면 10에선 9만 고려함.. 4도 고려해야 한다) 가장 가깝다고 dp[n]이 최소가 되는 것이 아니기 때문에 i*i<=n인 모든 경우의 수를 따져줘야 한다.

 

성공한 첫 번째 코드 16ms소요

#include <stdio.h>
#include <algorithm>
#include <limits.h>

using namespace std;

int arr[50001];

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

  arr[0] = 1;

  for (int i = 1; i <= n; i++)
  {
    arr[i] = INT_MAX;
  }
  for (int i = 1; i * i <= n; i++)
  {
    arr[i * i] = 1;
  }

  for (int i = 2; i <= n; i++)
  {
    if (arr[i] == 1)
      continue;

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

  printf("%d\n", arr[n]);
  return 0;
}

 

시간이 긴거 같아 다른 사람코드 보고 더 짧게 고쳐봤다. 8ms소요

#include <stdio.h>
#include <algorithm>

using namespace std;

int arr[50001];

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

  for (int i = 1; i <= n; i++)
  {
    arr[i] = i;
  }

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

  printf("%d\n", arr[n]);
  return 0;
}