[2018 홍익대학교 프로그래밍 경진대회] 16400번 소수 화폐

문제

소수나라는 특이하게 모든 소수(prime number)를 화폐 단위로 사용한다.

소수나라에 놀러 온 하나는 관광을 하다가 가격이 N인 물건을 발견하고 너무 마음에 들어 999983원을 내고 구매하려고 했다. 하지만 상점 주인이 거스름돈이 없어 정확히 N원을 지불해달라고 하였다.

물건을 구매하려던 하나는 소수나라의 화폐를 이용하여 N원을 정확히 만들 수 있는 방법의 가짓수가 얼마나 되는지 궁금해졌다.

하나를 도와 N원을 지불하기 위한 가짓수가 얼마나 되는지 구해보자.

단, 하나는 소수나라의 모든 화폐가 무한정 있다고 가정한다.

입력

구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다.

출력

소수나라의 화폐를 이용하여 지불할 수 있는 방법의 수를 출력한다.

단, 지불할 수 있는 방법의 수가 매우 크기때문에, 123,456,789로 나눈 나머지 값을 출력한다.

 

동전 DP 방법을 숙지하고 있는 것이 좋다.

최소 동전 개수를 구하는 것이 아닌 N을 만들기 위한 총 동전 개수를 구하는 문제.

1. 코인으로 지정된 코인들을 저장해 놓는다.

2. 기저점 0에 대해서 dp 값 1로 지정한다.

3. 겉은 동전 수로 돌면서 안에서는 동전 값 부터 목표 N까지 더 해가는 과정 반복.

 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;

int arr[40001];
int dp[40001];
vector<int> coin;
int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	int N;
	cin >> N;

	for (int i = 2; i <= N; i++)
	{
		for (int j = 2; i * j <= N; j++)
		{
			arr[i*j] = true;
		}
	}
	for (int i = 2; i <= N; i++)
		if (!arr[i])
			coin.push_back(i);

	dp[0] = 1;
	for (int i = 0; i < coin.size(); i++)
	{
		for (int j = coin[i]; j <= N; j++)
		{
			dp[j] = (dp[j] + dp[j - coin[i]]) % 123456789;
			dp[j] %= 123456789;
		}
	}
	cout << dp[N];
}