Baekjoon 3908 서로 다른 소수의 합

Link https://www.acmicpc.net/problem/3908 

결과 2052 KB / 0 ms

언어 C++ 17

 

풀이

에라토스테네스의 체를 이용해 소수를 먼저 구한다.

[선택된 개수][1120보다 죽은 수]를 저장하는 O(kn) DP를 구한다.

입력되는 값에 대하셔 해당 위치의 값을 출력한다.

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> primes;

const short MAX = 1120;
const short PRIME_MAX = 187;
const short SELECT_MAX = 14;

int prime_dp[SELECT_MAX + 1][MAX + 1];

void find_prime() {

	bool prime[MAX + 1] = { true, true };

	for (int i = 2; i < MAX; i++) {
		if (!prime[i]) {
			primes.push_back(i);
			for (int j = 2; i * j <= MAX; j++)
				prime[j*i] = true;
		}
	}

}

void init_dp() {

	prime_dp[0][0] = 1;

	for (int i = 0; i < PRIME_MAX; i++) {
		for (int j = MAX; j >= primes[i]; j--)
			for (int k = 1; k <= SELECT_MAX; k++)
				prime_dp[k][j] += prime_dp[k - 1][j - primes[i]];
	}
}

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

	// Init
	find_prime();
	init_dp();

	int n; cin >> n;

	while (n--)
	{
		int tar, cnt; cin >> tar >> cnt;

		cout << prime_dp[cnt][tar] << '\n';
	}
	return 0;
}