코드 복사/붙여넣기 하는 당신이 아름답습니다.

1415 : 사탕

풀이

.

코드

#include <cstdio>
#include <vector>
using namespace std;

int n, ccnt[10001];
long long d[500005];
vector<int> cvec;
bool p[500005];

void getprimes() {
	for (int i = 2; i <= 500000; i++) p[i] = 1;
	for (int i = 2; i*i <= 500000; i++)
		if (p[i]) for (int j = i*i; j <= 500000; j += i)
			p[j] = 0;
}

int main() {
	getprimes();

	scanf("%d", &n);
	int zcnt = 1;
	d[0] = 1;
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		if (x == 0) {
			zcnt++;
			continue;
		}
		if (ccnt[x] == 0) {
			cvec.push_back(x);
		}
		ccnt[x]++;
	}

	for (int now : cvec) {
		for (int i = 500000; i >= 0; i--) {
			for (int j = 1; j <= ccnt[now]; j++) {
				if (i - now * j < 0) break;
				d[i] += d[i - now * j];
			}
		}			
	}

	long long ans = 0;
	for (int i = 2; i <= 500000; i++) {
		//if (i < 30) printf("* %d\n", d[i]);
		if (p[i]) ans += d[i];
	}

	printf("%lld\n", ans * zcnt);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-06-24 22:09

Read more posts by this author