[백준]1699-제곱수의 합

실패코드를 먼저 보여드립니다.

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		cout << dp[i] << endl;
	}
	cout << dp[n] << endl;
}

 

 

반례가 있습니다.

12 = 3*2 + 1 + 1 + 1 = 4

12 = 2*2 + 2*2 + 2*2 = 3

명백하게 그리디적인 관점에서 문제를 해결나갈 수 없는 것을 보실 수 있습니다.

 

즉, 제곱값이 자신보다 작은 모든 제곱근들에서의 경우의 수를 비교해주어 결과값을 도출하여야 하는 문제입니다. 

 

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		for (int j = num-1; j >= 1; j--) {
			if( (1 + dp[i - j*j]) < dp[i] )
				dp[i] = 1 + dp[i - j*j];
		}
	}
	cout << dp[n] << endl;
}