[백준] 16400 - 소수 화폐

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

16400번: 소수 화폐

 

에라토스 테네스의 체 + dp 문제였다.

먼저 화폐의 종류를 구하기 위해 에라토스 테네스의 체로 N 이하의 소수를 걸러내자.

인접 리스트를 활용해 N 이하의 모든 소수를 담고, 해당 소수들로 지불할 수 있는 방법의 수를 dp로 구하면 된다.

 

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int a[40001], dp[40001];
vector<int> prime;

int main()
{
	int n;
	cin >> n;
	for (int i = 2; i * i <= 40000; i++)
	{
		if (!a[i])
		{
			for (int j = i * i; j <= 40000; j += i)
			{
				a[j] = 1;
			}
		}
	}
	for (int i = 2; i <= 40000; i++)
	{
		if (!a[i])
		{
			prime.push_back(i);
		}
	}
	int mod = 123456789;
	dp[0] = 1;
	for (int i = 0; i < prime.size(); i++)
	{
		for (int j = prime[i]; j <= n; j++)
		{
			dp[j] = (dp[j] % mod + dp[j - prime[i]] % mod) % mod;
		}
	}

	cout << dp[n];
}