백준 1699 C++ - 제곱수의 합

Intro

문제해결 및 소스코드

• 이 문제는 주어진 수를 제곱수들의 합으로 표현했을 때, 그 제곱수 항의 최소갯수를 구하는 문제다.

• 아래는 처음으로 이 문제를 접했을 때 생각했던 방식이다.

#include <iostream>
#include <cmath>
#define MAX 334

using namespace std;

/*              <문제해결>
        1. N을 어떤수의 제곱수들로 표현하기위해 arr배열에 1부터 316까지(N은 최대10만)의 제곱수를 저장
        2. N이 0이 될때까지 N의 제곱근으로 나누며 count를 증가
        
        ex) 12 =
                i)  12 - arr[sqr(12)] = 3, ans = 1, n = 3
                ii) 3 - arr[sqr(3)] = 2, ans = 2, n = 2
                iii)2 - arr[sqr(2)] = 1, ans = 3, n = 1
                iv) 1 - arr[sqr(1)] = 1, ans = 4, n = 0
                
                따라서 정답은 4
*/

int arr[MAX];
int ans;

int main()
{
	for (int i = 0;i < MAX;i++)
	{
		arr[i] = i * i;
	}

	int n;
	cin >> n;

	while (n > 0)
	{
		int x = sqrt(n);		// ex) 11 -> 3
		n -= arr[x];
		ans += 1;
	}

	cout << ans;
}

• 하지만 정답이 아니었고 왜 그런가 생각을 해보았더니, 반례가 존재했다. 예를들어 숫자 32를 생각해보자.
  • i) 32 - arr[sqr(32)] = 7, ans = 1, n = 7
  • ii) 7 - arr[sqr(7)] = 3, ans = 2, n = 3
  • iii) 3 - arr[sqr(3)] = 2, ans = 3, n = 2
  • iv) 2 - arr[sqr(2)] = 1, ans = 4, n = 1
  • v) 1 - arr[sqr(1)] = 1, ans = 5, n = 0
  • 따라서 정답은 5
• 우리는 32가 16 + 16으로, 최소항 갯수가 2개라는것을 알고있다. 그러면 어떤방식으로 문제를 해결해야할까

#include <iostream>

using namespace std;

/*              <문제해결>
        1. 어떤수 N을 제곱수의 합으로 표현하는 방법의 수를 dp[i]라고 하자.  
        2. DP방식으로 해결하기위해 dp[1]부터 dp[N] 까지를 초기화해준다.
        3. N은 N이하의 어떤수의 제곱의 합으로 표현할 수 있다. 

        - 32를 제곱수의 합으로 표현해보자.  

        1. 32는 31(32-1의제곱)을 만드는 방법의 최소갯수에 +1을 하면된다.
        2. 또는 28(32-2의제곱)을 만드는 방법의 최소갯수에 +1을 하면된다.
        3. 또는 23(32-3의제곱)을 만드는 방법의 최소갯수에 +1을 하면된다.
        4. 따라서 dp[32]를 계속 업데이트 해나가며, 업데이트된 dp와 업데이트될 dp중 최소를 고르면된다.
*/
int dp[100001];

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

	// 초기화
	for (int i = 1;i <= n;i++)
	{
		dp[i] = i;
	}

	// dp구하기
	for (int i = 1;i <= n;i++)
	{
        // 어떤수 이하의 제곱수까지
		for (int j = 1;j * j <= i;j++)
		{
			dp[i] = min(dp[i], dp[i - j * j] + 1);
		}
	}

	cout << dp[n];
}