BaekJoon 1699 제곱수의 합

Link https://www.acmicpc.net/problem/1699

소스결과 2392 KB / 56 ms

출처 BackJoon, ACM-ICPC 

언어 C++ 17

분류 다이나믹 프로그래밍

 

설명

어떤 자연수 N에 대하여 제곱수의 합으로 표현 할 때, 제곱수의 최소 개수를 구하는 문제

간단하게 생각하면 가장 큰 제곱수를 빼면서 0 ~ 3 사이의 결과가 나올 때 그 값을 더해 주면 된다.

 

위 알고리즘을 구현한 결과는 틀렸습니다.

알고보니 32 같은 반례가 존재했다.

위 알고리즘대로라면 32 = 25 + 9 + 1 + 1 로 4번이 나오지만 정답은 16 + 16 으로 2 이다.

 

결과에 대해서 검증하는 과정이 필요하다.

 

알고리즘

1. n 을 입력 받는다.

2. DP Table을 초기화 한다.

 2 - 1 현재 초기화 하는 값 x가 제곱수인지 확인한다. 제곱수라면 1 반환,

 2 - 2 dp[x] 가 전부 1일 경우로 생각하고 dp[x] 를 x으로 초기화

 2 - 3 x에 대해서 2 부터 sqrt(x) 까지 제곱한 값을 뺀 값을 x로 삼아 재귀 호출

 2 - 4 결과 값이 현재 dp[x] 보다 작다면 dp[x]에 결과값을 대입

 2 - 5 최종 dp[n]을 반환

3. dp[n]을 출력

 

소스코드

#include <iostream>
#include <cmath>

using namespace std;

const int MAX = 100000;
int dp[MAX + 1];

int min(int a, int b) { return a < b ? a : b; }

int func(int n)
{
	if (dp[n]) return dp[n];

	if (n == pow(int(sqrt(n)), 2))
		return 1;

	for (int i = 2; i <= sqrt(n); i++) {
		int res = func(n - (i * i)) + 1;
		if (dp[n] > res)
			dp[n] = res;
	}

	return dp[n];
}

int main()
{
	int n;

	cin >> n;

	for (int i = 0; i < MAX + 1; i++)
		dp[i] = i;

	// dp Init
	for (int i = 4; i < MAX + 1; i++)
		dp[i] = func(i);
		
	cout << dp[n];

	return 0;
}