BOJ 1415 - 사탕

BOJ 2624 문제를 먼저 푸는 것을 추천합니다.

============================================================

이 문제 역시 동전 바꿔주기 문제와 완전 동일하다. 단, 소수가 추가됐긴 했지만, 이는 에라스토테네스의 체로 구할 수 있다.

각 사탕에 대해서 hashing을 해줘야하며(몇 번째 사탕인지 등), 이는 map또는 vector, array 해싱으로 처리할 수 있다.

기본적인 아이디어는 캔디 종류 하나씩 처리를 해나가며 처리한다.

현재 처리해야 하는 캔디가 k번째 캔디라면 이전에 처리된 0부터 500000까지(50*10000) 가능한 가격에 대해 k번째 캔디의 가격을 더한다. 더할 때도, 같은 캔디가 여러개 있을 수 있으므로, k번째 캔디의 수가 cnt[k]라면 1부터 cnt[k]를 살 수 있으므로, 이전에 있던 가격에 더해주는 방식을 취해준다.

dp[가격]

으로 1차원으로 잡아주고, 단순히 순회하면서 값을 갱신해주기만 하면 된다.

또 여기에 함정이 있는게, 가격이 0이 될 수도 있으므로, 아무리 cnt[k]를 늘려봤자 다음 dp[가격]은 dp[0]이 되므로(제자리 걸음) 0을 따로 계산해서 (0의 개수+1) 만큼 나중에 곱해준다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
using ll = long long;
const int MAX_V = 500001;
int min_v(int a, int b) { return a < b ? a : b; }
int main() {
	bool prime[MAX_V] = { 1,1 };
	int cnts[10001] = {}, L;
	vector<int> candies;
	int i, j, k, D, N, maxi=0;
	ll dp[MAX_V] = {1, };
	for (i = 4; i < MAX_V; i += 2)
		prime[i] = 1;
	for (i = 3; i < MAX_V; i += 2) {
		if (prime[i]) continue;
		for (ll j = 1LL*i * i; j < MAX_V; j += i*2)
			prime[j] = 1;
	}
	int zcnt = 1;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &D);
		if (D == 0) {
			zcnt++;
			continue;
		}
		if (cnts[D] == 0)
			candies.push_back(D);
		cnts[D]++;
	}
	L = candies.size();
	for (i = 0; i < L; i++) {
		for (j = maxi; j >= 0; j--) {
			for (k = 1; k <= cnts[candies[i]]; k++) {
				if (j + k*candies[i] >= MAX_V) break;
				dp[j + k*candies[i]] += dp[j];
			}
		}
		maxi += candies[i] * cnts[candies[i]];
		maxi = min_v(maxi, MAX_V - 1);
	}
	ll ans = 0;
	for (i = 2; i < MAX_V; i++)
		if (!prime[i]) ans += dp[i];
	ans *= zcnt;
	printf("%lld", ans);
	return 0;
}