[백준] 17626.cpp : Four Squares

www.acmicpc.net/problem/17626

17626번: Four Squares

#include <iostream>
using namespace std;

// 입력 받은 자연수까지의 모든 최솟값들을 구해놓을 배열
int ans[50001] = {0, 1, 2, 3, 1, 2};
// 제곱근들에 대한 배열
int sqr[225] = {0};

// i 번쨰에 대한 최솟값을 구하는 함수
int cntMin(int idx)
{
  int min = 4;
  for(int i = 1 ; i * i <= idx ; i++)
  {
    // 각 제곱값들 별로 완전 탐색, 제곱값을 뺀 값에 대한 최솟값은 이미 dp 배열에 존재
    int n = ans[idx - sqr[i]];
    if(n < min) min = n;
  }
  // 최솟값(min) + 특정 제곱값(1)
  return min + 1;
}

int main(void)
{
  int n;
  cin >> n;

  // 각 제곱값들은 갯수를 1로 초기화시켜줌
  for(int i = 1 ; i < 225 ; i++)
  {
    sqr[i] = i * i;
    ans[i * i] = 1;
  }
  // 1~n 까지 최솟값들을 배열에 저장
  for(int i = 6 ; i <= n ; i++)
  {
    // 제곱값들은 하지 않음
    if(ans[i] == 0)
    {
      ans[i] = cntMin(i);
    }
  }

  cout << ans[n] << '\n';
}

 

[Approach]

1. 그리디한 느낌으로 가장 큰 제곱근부터 찾아서 구해나가거나  /  50000 이면 완전탐색으로 전부 다 찾아보는 방법이 있을 것 같다.

     생각해보니 둘 다 동시에 적용해야 할 듯. 재귀로 빠지면 함수 스택이 너무 깊어질 것 같다.

     도저히 안되겠는데, 정말 dp 배열 5만개를 다 만드는게 맞는걸까?

     결국 DP 배열을 써서 맞긴 했는데, 뭔가 찝찝하다.

 

[Point]

1. 50000개 채우는게 생각보다 시간이 그렇게 오래걸리는 일은 아닌 것 같다.

2. 결국 이 문제도 완전 탐색 하는게 껄끄러워서 다른 방법을 계속 생각하다 오래 걸렸는데, 이 마인드를 어떻게 고쳐야 할지 모르겠다.