백준 19699 소-난다!

www.acmicpc.net/problem/19699

19699번: 소-난다!

최근에 추가된 문제 중 하나이다.

처음엔 백트래킹으로 풀었는데 안 풀려서 그냥 next_permutation으로 풀었다.

입력받은 수를 정렬시키고 m번만큼 sum변수에 더해줘서 그 sum이 소수이면 ans에 추가해준다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool vis[10001];

void era() {
	fill(vis, vis + 10001, true);
	vis[0] = vis[1] = false;
	for (int i = 2; i * i <= 10000; i++) {
		if (vis[i]) {
			for (int j = i * 2; j <= 10000; j += i) vis[j] = false;
		}
	}
}

int main() {
	int n, m, x;
	vector<int> ar, ans;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> x; ar.push_back(x);
	}
	era();
	sort(ar.begin(), ar.end());
	do {
		int sum = 0;
		for (int i = 0; i < m; i++) {
			sum += ar[i];
		}
		if (vis[sum]) ans.push_back(sum);

	} while (next_permutation(ar.begin(), ar.end()));

	if (ans.empty()) cout << -1 << endl;
	else {
		sort(ans.begin(), ans.end());
		ans.erase(unique(ans.begin(), ans.end()), ans.end());
		for (int i = 0; i < (int)ans.size(); i++) cout << ans[i] << ' ';
	}

	return 0;
}

미리 에라토스테네스의 체로 

1 <= H <= 1000이니

1000 * 9 만큼 소수를 구해준다.

 

++ 2020.10.11 추가

 

문제를 다시 풀어보던 중 DFS로 풀어보고 싶어서 풀어봤다.

 

• 체로 1만까지 소수를 구한다
• DFS를 통해 cnt가 m이 되면 m만큼 경우의 수를 추출해서 합한 뒤에 소수이면 ans에 넣어준다
• 정렬 후 중복을 제거한 뒤 출력한다

 

와 같은 방식으로 풀었다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> ar, ans, ar2;
vector<bool> sieve(10001), vis;
int n, m;

void era() {
	fill(sieve.begin(), sieve.end(), true);
	sieve[0] = sieve[1] = false;
	for (int i = 0; i * i <= 10000; i++) {
		if (sieve[i]) {
			for (int j = i * 2; j <= 10000; j += i) sieve[j] = false;
		}
	}
}

void DFS(int cnt, int idx) {
	if (cnt == m) {
		int sum = 0;
		for (int i = 0; i < m; i++) {
			sum += ar2[i];
		}
		if (sieve[sum]) ans.push_back(sum);
	}
	for (int i = idx; i < n; i++) {
		if (!vis[i]) {
			vis[i] = true;
			ar2[cnt] = ar[i];
			DFS(cnt + 1, i);
			vis[i] = false;
		}
	}
}

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

	cin >> n >> m;
	ar.resize(n);
	ar2.resize(n);
	vis.resize(n);
	for (int i = 0; i < n; i++) cin >> ar[i];
	era();

	DFS(0, 0);

	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());

	if (!ans.size()) cout << -1 << endl;
	else {
		for (auto i : ans) cout << i << ' ';
	}

	return 0;
}

 

DFS를 조합으로 만들어서 위에 next_permutation으로 푼 것보단 시간 복잡도가 조금 덜 걸렸다.