[백준] 제곱수의 합

제곱수의 합 (실 3) : https://www.acmicpc.net/problem/1699

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제.

난이도는 실버 3인데 골드5인 합분해보다 어려웠고, 헤맸다.

 

---

1. 문제 분석 및 접근

 

최적화문제. 최적 부분 구조를 가지고 있다. 왜냐하면 이전 선택과 현재 선택은 독립적이며, 이전 선택에 관계없이 현재 선택에서 선택의 최솟값만을 도출해내면 되기 때문이다.

또한 그리디하게, 매번 가장 큰 제곱수를 선택하는 방법을 생각했는데, 바로 반례가 나오더라.

예로 들어 n = 32인 경우,

그리디한 접근 : 25 + 4 + 1 + 1 + 1 = 5개

정답 : 16 + 16 = 2개

 

따라서, 만들어질 수 있는 모든 경우의 수를 살펴 보아 그 중 선택의 최솟값을 도출해내야 한다.

 

2. 완전 탐색

 

#include <iostream>
#include <math.h>

using namespace std;

int maxSquared(int n, int cnt) 
// 현재 숫자가 n이고, 이전 최소 갯수가 cnt일 때,
// 제곱수들을 선택하여 얻을 수 있는 제곱수 합의 항 최소 갯수를 반환한다.
{
  if (n == 0)
    return cnt;

  int smallest = 1000000;

  for (int selectedNum = sqrt(n); selectedNum > 0; selectedNum--)
  // selectedNum = sqrt(n)해준 이유는, selectedNum의 제곱은 n보다 무조건 같거나 작아야 하므로!
  {
    int cand = maxSquared(n - selectedNum * selectedNum, cnt + 1);
    smallest = min(smallest, cand);
  }
  return smallest;
}

int main(void)
{
  int N;

  cin >> N;

  cout << maxSquared(N, 0) << '\n';

  return 0;
}

 

3. DP화

 

DP 최적화 레시피(https://sanghoonly.tistory.com/37)를 이용.

 

1. 완전 탐색 알고리즘 설계 => 설계 완료!

2. 반환 값의 정의 수정 => 앞으로 남은 문제들에 대한 최적해를 구하도록 함수 변환.

3. 파라미터를 줄여서 더욱 함수가 중복되도록 구현.

4. 메모이제이션 적용.

 

#include <iostream>
#include <math.h>
#include <memory.h>

int cache[100001];

using namespace std;

int maxSquared(int n)
// 파라미터였던 cnt를 삭제.
// 이전 최소 갯수에 상관없이, n에 대하여 제곱수들의 최소 항 갯수를 반환.
{
  if (n == 0)
    return 0;

  int &ret = cache[n];

  if (ret != -1)
    return ret;

  ret = 1000000;

  for (int selectedNum = sqrt(n); selectedNum > 0; selectedNum--)
  {
    int cand = maxSquared(n - (selectedNum * selectedNum)) + 1;
    ret = min(ret, cand);
  }
  return ret;
}

int main(void)
{
  int N;

  cin >> N;

  memset(cache, -1, sizeof(cache));

  cout << maxSquared(N) << '\n';

  return 0;
}