1699_제곱수의 합

▶실버2

풀이

ex) n = 12라면,

① dp[12 - 1*1] = dp[11], dp[12 - 2*2] = dp[8], dp[12 - 3*3] = dp[4] 중 가장 작은 값에 +1한 값이 dp[12]가 된다.

하지만 dp[1~11] 의 값을 알기 위해서는 1부터 1씩 증가하며 dp값을 구하는 작업을 먼저 진행한다.

i = 1) dp[1] = 1

i = 2) dp[2]: dp[2 - 1*1] + 1= dp[1] + 1 = 2

i = 3) dp[3]: dp[3 - 1*1] + 1 = dp[2] + 1 = 3 

...

이런식으로 n까지 진행하는 과정에서, i 값에 따라 ①을 진행한다.

또, 주의할 점은 dp의 값을 dp값이 가질 수 있는 최대의 항의 수 개수로 초기화 해야한다. (dp[i] = i)

코드

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

int dp[100001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		//최대의 항 개수를 dp값으로 초기화
		dp[i] = i;
		//i의 제곱근보다 작은 수를 차례로 탐색하며 최소 항 개수를 가지면 값 갱신
		for (int j = 1; j <= int(sqrt(i)); j++) {
			if (dp[i] > dp[i - j * j] + 1) {
				dp[i] = dp[i - j * j] + 1;
			}
		}
	}
	cout << dp[n];
}