[백준] 19699번 소-난다!

변수 설정

 

몸무게의 합이 소수인 경우만 출력해야 하므로 몸무게의 합이 소수인지 판별해야한다. 에라토스테네스의 체를 사용하여 소수의 값들을 초기화한다.

 

중복을 허용하지 않는 조합을 사용하여 tmp(선택한 소들의 집합)에 몸무게를 추가하고 M마리의 소를 선택했을 때 M마리 소들의 몸무게를 합하여 소수인지, 중복되는지 확인한다.

 

정답인 배열을 sort를 사용하여 내림차순으로 정렬 후 출력한다.

 

 

전체코드

#include <bits/stdc++.h>

using namespace std;

vector<bool> isPrime(10005, true);	// 소수인지 판별하는 배열
vector<bool> check(10005, false);	// 중복 몸무게 확인하는 배열
vector<int> cow(10);	// 소들의 몸무게
vector<int> tmp(10);	// M마리 소들의 몸무게
vector<int> answer;
int N, M;

// 에라토스테네스의 체로 소수 초기화
void initPrime() {
	for (int i = 2; i <= sqrt(10000); i++) {
		if (isPrime[i]) {
			for (int j = i * 2; j <= 10000; j += i)
				isPrime[j] = false;
		}
	}
}

void func(int depth, int next) {
	if (depth == M) {	// M마리의 소를 선택했을 경우
		int sum = 0;
		for (int i = 0; i < M; i++) {
			sum += tmp[i];
		}
		if (isPrime[sum] and !check[sum]) {	// M마리의 소들의 몸무게가 소수고 몸무게가 중복되지 않을 경우
			answer.push_back(sum);
			check[sum] = true;
		}
		return;
	}

	for (int i = next; i <= N; i++) {
		tmp[depth] = cow[i];
		func(depth + 1, i + 1);
	}
}

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

	initPrime();

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> cow[i];
	}

	func(0, 1);

	sort(answer.begin(), answer.end());	// 내림차순으로 정렬

	if (answer.empty())	// 몸무게의 합이 소수인 경우가 없는 경우
		cout << "-1";
	else {
		for (auto num : answer)
			cout << num << '\n';
	}

	return 0;
}