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

 

 

<코드>

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

int N;
int dp[100001];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

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

	for (int i = 3; i <= N; i++)
	{
		dp[i] = dp[i - 1] + 1;
		
		int x = 2;
		while ((int)pow(x, 2) <= i)
		{
			dp[i] = min(dp[i], 1 + dp[i - (int)pow(x, 2)]);
			x++;
		}
	}
	
	cout << dp[N];
	
}

 

풀이 방법

 

알고리즘 예시

43이 입력으로 주어졌을 때 43 = 5^2 + 3^2 + 3^2 으로 dp[43] = 3이 답이고, 43이 될 수 있는 경우의 수를 따져보면

• dp[43] = dp[1] +dp[42]
• dp[43] = dp[4] +dp[39]
• dp[43] = dp[9] +dp[34]
• dp[43] = dp[16] +dp[27]
• dp[43] = dp[25] +dp[18]

이 중에서 가장 작은 값을 선택하면 정답이다.

 

 

www.acmicpc.net/problem/1699

1699번: 제곱수의 합