[백준 DP] 1699번 - 제곱수의 합

1699번 - 제곱수의 합

---

<문제>

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

1699번: 제곱수의 합

 

<문제 풀이>

 

점화식: dp[i] = dp[j * j] + dp[i - j * j]  = 1 + dp[i - j * j]

---

<코드>

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

int N;
int dp[100001] = { 0, };

int solution(int n) { //제곱근이 맞으면 0, 아니면 1
	long long re;
	long long a = sqrt(n);

	if (a * a == n) re = 0;
	else re = 1;

	return re;
}

int main() {
	cin >> N;

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

	for (int i = 4; i <= N; i++) { //제곱근 판별, 제곱근이 맞으면 dp에 1 대입 
		if (solution(i) == 0) dp[i] = 1;
	}

	for (int i = 1; i <= N; i++) {
		//dp[i] 갱신 
		for (int j = 1; j*j <= i; j++) {
			if (dp[i] > dp[j * j] + dp[i - j * j]) {
				dp[i] = dp[j * j] + dp[i - j * j];

			}
		}
	}

	cout << dp[N] << endl;

	return 0;
}

 

 

 

2022.11.24