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

 

문제

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

1699번: 제곱수의 합

 

풀이 

 

 

 

dp[i]: N을 제곱수로 나눴을 때 가장 작은 제곱 항수를 저장하는 변수

- dp[i]은 초기값으로 N을 가진다. (1 제곱 * N항 )

 

그리고 나서 재귀관계식을 찾아주었다. 

나는 N이 13일 때까지 쭉 나열하며 재귀관계식을 찾을 수 있었다. 

 

- N에서 나눠떨어지는 숫자가 있으면 나눠떨어지는 숫자는 무조건 1이다. (4, 8, 16, 25..)

N에서 나눠떨어지는 숫자를 뺀 값 (N-(j*j)을 dp에서 빼와 더하면 된다. 

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

 

소스 코드

#include <iostream>
#include <cmath> // min

int main(){

	int dp[100001];
	int n; std::cin >> n;

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

 	std::cout << dp[n];

	return 0;
}