[백준] 1699번 제곱수의 합

1699번: 제곱수의 합

동전 2 문제와 같은 방식으로 점화식

DP[n]=최솟값(DP[n], DP[n-현재 제곱수] + 1)

으로 풀면 되는 문제이다.

제곱수들을 동전으로 생각하고 자연수 N을 목표하는 가치 K로 생각하면 된다.

 

N이 13이라면 제곱수들은 1, 4, 9로 이루어져 있어야 하고

N이 50이라면 제곱수들은 1, 4, 9, 16, 25, 36, 49로 이루어져 있어야 한다.

이 제곱수들을 조합하여 1~N까지의 수를 만들어 나가며

필요한 최소 개수를 저장시키면 된다.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
	int N;
	cin >> N;
	int dp[100001] = { 0 };
	for (int i = 1; i <= N; i++) dp[i] = i;
	for (int i = 2; i <= sqrt(N); i++) {
		for (int j = i * i; j <= N; j++) {
			dp[j] = min(dp[j], dp[j - i * i] + 1);
		}
	}
	cout << dp[N];
	return 0;
}