[C/C++] 백준 3908번 - 서로 다른 소수의 합

 

 

<코드>

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

int t, n, k;
int dp[1121][15];
vector<int> prime_num;

void find()
{
	bool flag;

	for (int i = 2; i <= 1120; i++)
	{
		flag = true;

		for (int j = 2; j < i; j++)
		{
			if (i % j == 0)
			{
				flag = false;
				break;
			}
		}

		if (flag == true)
		{
			prime_num.push_back(i);
		}	
	}
}

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

	find();

	dp[0][0] = 1;

	for (int i = 0; i < prime_num.size(); i++)
		for (int j = 1120; j >= prime_num[i]; j--)
			for (int k = 1; k <= 14; k++)
				dp[j][k] += dp[j - prime_num[i]][k - 1];
	cin >> t;
	while (t--)
	{
		cin >> n >> k;
		cout << dp[n][k] << '\n';
	}
	

}

 

 

 

www.acmicpc.net/problem/3908

3908번: 서로 다른 소수의 합