백준 1699번 _ 제곱수의 합

2020-05-09 · 배운 것 · 2분 읽기

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

1699번: 제곱수의 합

풀이방법

제곱수를 미리 구해놓음

void powNumberInit()
{
	powNumber[1] = true;

	for (int i = 4; i <= n; i++)
	{
		int tmp = (int)sqrt(i);
		if (i  == tmp*tmp)
			powNumber[i] = true;
	}
}

그이후 동전 2와 똑같이 풀면 됨.
https://blog.fxjodo.com/blog/131/

백준 2294번 _ 동전 2

전체코드

#include <iostream>
#include <algorithm>
#include <math.h>

#define INF 987654321

using namespace std;
bool powNumber[100001];
int n;
int dp[100001];

void dpInit()
{
	for (int i = 1; i <= n; i++)
		dp[i] = INF;
}

void powNumberInit()
{
	powNumber[1] = true;

	for (int i = 4; i <= n; i++)
	{
		int tmp = (int)sqrt(i);
		if (i  == tmp*tmp)
			powNumber[i] = true;
	}
}

void solve()
{
	for (int i = 1; i <= n; i++)
	{
		if (powNumber[i] == false)
			continue;

		for (int j = 1; j <= n; j++)
		{
			if (j % i == 0)
				dp[j] = min(j / i, dp[j]);

			if (dp[j] == INF)
				continue;

			if (j + i <= n)
				dp[j + i] = min(dp[j + i], dp[j] + 1);
		}
	}
}

int main()
{
	cin >> n;
	powNumberInit();
	dpInit();
	solve();
	cout << dp[n];
	return 0;
}