[백준/C++] 1699번: 제곱수의 합

문제

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

---

문제 요약

자연수 N을 제곱수들의 합으로 나타내는 방법 중 그 항의 최소 개수를 구하는 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int dp[100010];

int n;

int main() {

	cin >> n;

	for (int i = 1; i <= n; i++) {
		dp[i] = i;

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

	cout << dp[n];
	
	return 0;
}

---

코드 설명

1. dp[i]를 자연수 i를 제곱수들의 합으로 표현했을 때, 그 항의 최소 개수를 저장하는 DP 테이블로 정의한다.

 

2. dp[i]를 1로만 더해진 항의 개수인 i로 초기화한다.

 

3. dp[i] 값을 찾기 위해, 1부터 제곱 수를 탐색하며 dp[i - j * j] + 1 값과 비교한다.

 

dp[i - j * j] + 1

=> i - j * j를 제곱수들의 합으로 표현했을 때의 항들의 최소 개수 + j * j