[BOJ 1415 // C++] 사탕

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1415번 문제인 사탕이다.
문제는 아래 링크를 확인하자.

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

1415번: 사탕

사탕의 개수가 50 이하이고 가격이 10,000 이하이므로, 사탕의 가격이 모두 다르다면 미리 소수들을 계산해두고 knapsack DP를 이용해 간단히 문제를 해결할 수 있다.

 

마찬가지로, 가격이 같은 사탕이 있다면 해당 가격의 사탕으로 만들 수 있는 가격들을 같은 방식으로 한번에 처리하는 것으로 문제를 해결할 수 있다.

 

가격이 0인 사탕이 있을 수 있다는 점에 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

bool sieve[500001];

ll cnt[500001];
int price[10001];

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

	sieve[0] = sieve[1] = 1;
	for (int i = 2; i < 707; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 500001; j += i) sieve[j] = 1;
	}

	cnt[0] = 1;
	int N; cin >> N;
	while (N--) {
		int p; cin >> p;
		price[p]++;
	}

	for (int i = 10000; i > 0; i--) {
		vector<int> vec;
		int p = 0;
		int& pcnt = price[i];
		while (pcnt--) {
			p += i;
			vec.emplace_back(p);
		}
		if (vec.empty()) continue;
		for (int j = 500000; j > 0; j--) {
			for (auto x : vec) {
				if (j - x < 0) break;
				cnt[j] += cnt[j - x];
			}
		}
	}
	
	ll ans = 0;
	for (int i = 2; i < 500000; i++) {
		if (sieve[i]) continue;
		ans += cnt[i];
	}

	cout << ans * (price[0] + 1);
}