[백준] 1699: 제곱수의 합(C++)

문제

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

해결방법

N이 주어졌을 때, N보다 작거나 같은 제곱수들을 모두 고려해야 한다.

 

먼저 dp[i]를 제곱수들의 합으로 표현할 때 최소 개수라고 정의한다. dp[i]의 최댓값은 모두 1로만 이루어진 경우이므로 초기값을 i로 설정한다. 그러면 d[0]은 0, d[1]은 1, d[2]는 2, d[3]은 3으로 초기화할 수 있다.

 

이후, 가장 큰 제곱수 j^2을 선택하고 남은 값을 최소 개수로 만드는 방식으로 접근한다.

 

d[i] = min(dp[i], d[i - j*j] + 1)

 

이 점화식은 i에서 j의 제곱수를 뺐을 때, 남은 부분 d[i - j*j]의 최소 제곱수 개수에 1(i보다 작은 제곱수)을 더한 값 중에서 최소값을 선택하는 것이다.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, dp[100001];
	cin >> n;

	dp[0] = 0;
	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;
}