백준 1699 c++ 제곱수의 합

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

---

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

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

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

---

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
	vector<int> dp(100001,9999);//제곱합의 최솟값을 담을 벡터
	dp[1] = 1;
	int N;
	cin >> N;

	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j * j< i+1; j++)
		{
			if (i == j * j)
			{
				dp[i] = 1;
				break;
			}
			dp[i] = min(dp[i - j * j] + 1,dp[i]);
		}
	}
	cout << dp[N];
}

---

반례의 경우 12가 있다.

12의 경우 dp[12] 는 4가 아닌 3이다. 즉 가장 높은 제곱수로 나누는 것이 꼭 정답이 아니란 거다

틀린 답 : 12 = 3^2 + 1^2 + 1^2 + 1^2 = 4 =dp[9]+dp[3]

맞은 답 : 12 = 2^2 + 2^2 + 2^2 = 3 = dp[4]+dp[8]

처음에는 O(N^2) 방식으로 풀었는데 시간초과가 떴다

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
	vector<int> dp(100001,9999);
	dp[1] = 1;
	int N;
	cin >> N;
    
	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j < i/2+1; j++)
		{
			if (i == j * j)
			{
				dp[i] = 1;
				break;
			}
			dp[i] = min(dp[i], dp[i - j] + dp[j]);
		}
	}
	cout << dp[N];
}

dp[12]

dp[11] + dp[1]

dp[10] + dp[2]

dp[9] + dp[3]

dp[8] + dp[4]

dp[7] + dp[5]

dp[6] + dp[6]        의 모든 케이스를 돌려 보았기 때문이다.

 

이런 방법이 아닌 

dp[12]

dp[1^2]+dp[11]

dp[2^2]+dp[8]

dp[3^2]+dp[3]       이 정도의 케이스만을 봐도 된다

 

그 이유는 12 의 경우

12 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2

12 = 2^2 + 2^2 + 2^2

12 = 3^2 + 1^2 + 1^2 + 1^2

이렇게 3가지의 케이스가 있다

여기서 dp[i] = min(dp[i - j * j] + 1,dp[i]);  식은 위에 부터 각각

1^2  ,  2^2  ,  3^2  를 빼준 것을 의미한다 

즉 모든 케이스를 살펴볼 필요 없이 O(N^1.5) 의 시간복잡도로 단축시킬 수 있다.