[BOJ] 16400번: 소수 화폐

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

16400번: 소수 화폐

---

접근 방법

dp로 풀어야겠다는 생각은 바로 했는데, 내가 세운 dp식이 중복을 처리해주지 못했다. 여기서 '동전 dp' 문제가 떠올랐어야 하는데, 3달 전에 풀어놓고 까먹고 있었다.. 화가 난다..게다가 3달 전에도 풀이를 보고 풀었었다..

---

풀이 / 시간 복잡도

dp[j] += dp[j - i] (i는 1 <= i <= n의 소수, i <= j <= n) 의 점화식을 이용해 O(n^2) 으로 풀 수 있다. 

i원을 더할 때에는 i원 보다 작거나 같은 수만 처리되었기 때문에 중복이 생기지 않는다.

---

 코드

ll n;
ll d[40005];
bool p[40005];

void solve()
{
	cin >> n;

	p[0] = p[1] = 0;
	for (ll i = 2; i <= n; i++)
	{
		p[i] = 1;
		for (ll j = 2; j * j <= i; j++)
			if (i % j == 0)
			{
				p[i] = 0;
				break;
			}
	}
	
	d[0] = 1;
	for (ll i = 1; i <= n; i++)
	{
		if (p[i])
		{
			for (ll j = i; j <= n; j++)
			{
				d[j] += d[j - i];
				d[j] %= MOD;
			}
		}
	}
	cout << d[n];
}