[C++] 백준 19699번: 소-난다!

문제 링크

19699번: 소-난다!

문제 요약

N마리의 소 중에서 M마리의 소를 골랐을 때, 그 몸무게의 합이 소수가 되는 경우, 몸무게를 오름차순으로 출력해야 한다.

접근 방법

전형적인 백트래킹 문제와 전형적인 에라토스테네스의 체 문제를 합친 문제였습니다. 소가 최대 9마리고, 각 소의 몸무게의 최대값도 1000이기 때문에, 전처리로 9000까지의 소수를 모두 구해둡니다. 그 다음에 백트래킹을 통해서 M마리의 소를 뽑아내고, 그 소의 몸무게의 합을 구합니다. 이 합이 소수라면 저장해서 마지막에 오름차순으로 출력해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 9001;
int n, m;
bool visited[MAX];
vector<int> v;
set<int> s;

void init(void)
{
	visited[0] = visited[1] = true;
	for (int i = 2; i <= sqrt(MAX); i++)
		for (int j = i * 2; j < MAX; j += i)
			if (!visited[j])
				visited[j] = true;
}

void func(int cnt, int idx, int sum)
{
	if (cnt == m)
	{
		if(!visited[sum])
			s.insert(sum);
		return;
	}

	for (int i = idx; i < n; i++)
		func(cnt + 1, i + 1, sum + v[i]);
}

int main(void)
{
	init();
	cin >> n >> m;

	v.resize(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];

	func(0, 0, 0);

	for (auto& i : s)
		cout << i << ' ';

	if (s.empty())
		cout << -1 << '\n';

	return 0;
}