[BOJ] 1699번_제곱수의 합_DP (C++)

[문제]

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

모든 자연수는 그 수보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 입력받은 자연수 N을 제곱수들의 합으로 나타낼 때, 항의 최소개수를 구하는 문제이다.

[사용 알고리즘]

DP(다이나믹 프로그래밍)

[풀이 핵심]

• 먼저 0은 자연수가 아니므로 만들 수 없기 때문에 0으로 초기화한다. 그리고 1,2,3은 1의 제곱의 합으로 밖에 만들 수 없기 때문에 각각 1,2,3으로 초기화해준다.
• 4부터는 기존에 초기화된 값과 jj라는 제곱수를 사용했을 때 중 항이 더 적은 값으로 갱신해준다. 점화식에서 dp[i-(jj)+1]의 의미는 j*j라는 제곱수를 사용했을 때의 항의 개수(뒤에 +1을 해주는 이유는 j*j라는 제곱수가 하나의 항이기때문)이다.

[코드]

//boj1699번_제곱수의 합_dp

#include<iostream>

using namespace std;

int dp[100001];

int main() {
	int N;
	cin >> N;

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;

	for (int i = 4; i <= N; i++) {
		dp[i] = i;
	}

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

	return 0;
}