[BOJ/C++] 1699 - 제곱수의 합

1. 문제 링크

BOJ 1699번 - 제곱수의 합

2. 난이도

S2

3. 걸린 시간

30분

4. 문제 풀이

#include <bits/stdc++.h>
using namespace std;
#define INF int(1e9)

int n;
int dp[100'001];

int main() {
	cin >> n;

	fill(dp, dp+100'001, INF);
	dp[0] = 0;

	for (int i = 1; i <= n; i++) {
		int j = 0;
		while (j <= i) {
			if (j * j > i) break;
			dp[i] = min(dp[i - j * j] + 1, dp[i]);
			j++;
		}
	}
	cout << dp[n] << '\n';
}

가장 작은 횟수로 제곱수의 합으로 표현될 때의 횟수를 찾는 문제이다.

이는 DP로 구현할 수 있으며, 점화식은 다음과 같이 나온다.

j의 제곱값이 i보다 작을 동안만 순회하며, 모든 경우의 수를 확인해준다. 그리고 dp[i] 값을 최소로 갱신해준다.