[백준OJ] 16400번 소수 화폐

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

16400번: 소수 화폐

---

 

풀이

이 문제를 풀기전에 동전문제를 풀고오면 쉽다. 왜냐면 경우의수를 구하는 알고리즘이 같기때문이다.

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

2293번: 동전 1

소수판별 알고리즘과 DP를 혼용하여 문제를 해결하였다. 하지만 N값이 최대 40000이기때문에, 각 숫자마다 소수인지 판별을 하면 시간이 오래걸리므로, ,에라토스테네스의 체 알고리즘을 이용했다.

https://khu98.tistory.com/227

[알고리즘] 소수판별 알고리즘 C++

에라토스테네스의 체 알고리즘을 이용하여 모든 소수들을 Vector에 넣은 뒤, 동전 문제처럼 DP를 이용하여 만들 수 있는 경우의 수를 모두 구해주었다.

 

코드

#include <iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define MOD 123456789
using namespace std;

int n;
bool isPrime[40001] = { 0 };
long long dp[40001] = { 0 };
vector<int> prime;

void SOE() {
	memset(isPrime, true, sizeof(isPrime));
	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {
			prime.push_back(i);
			for (int j = i * 2; j <= n; j += i) {
				isPrime[j] = false;
			}
		}
	}
}


void input() {
	cin >> n;
}

void solution() {
	dp[0] = 1;
	for (int i = 0; i < prime.size(); i++) {
		int now = prime[i];

		for (int j = now; j <= n; j++) {
			dp[j] = (dp[j] + dp[j - now]) % MOD;
		}
	}
	cout << dp[n];
}

void solve() {
	input();
	SOE();
	solution();
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	solve();

	return 0;
}