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

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

 

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

bool p[10000];
int n, m;
vector<int> h;
vector<bool> chk;
set<int> ans;

void dfs(int idx, int res) {
    if (idx == m) {
        if (res < 10000 && p[res]) ans.insert(res);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!chk[i]) {
            chk[i] = 1;
            dfs(idx + 1, res + h[i]);
            chk[i] = 0;
        }
    }
}

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

    fill_n(p, 10000, 1);
    p[0] = p[1] = 0;

    for (int i = 2; i < 5000; i++) {
        int tmp = i * 2;
        while (tmp < 10000) {
            p[tmp] = 0;
            tmp += i;
        }
    }

    cin >> n >> m;
    h = vector<int>(n);
    chk = vector<bool>(n, false);
    for (int i = 0; i < n; i++) cin >> h[i];
    sort(h.begin(), h.end());

    dfs(0, 0);
    if (ans.empty()) {
        cout << -1 << '\n';
    } else {
        for (int x: ans) cout << x << ' ';
        cout << '\n';
    }
}

우선 에라토스테네스 체로 1부터 10000까지 범위에서 소수를 찾았다. 그 후 dfs를 통해 가능한 모든 합들을 살펴보면서 소수인지 아닌지 체크한다. 소수가 중복되면 안 되기 때문에 ans를 set으로 하였고, C++에서 set은 알아서 오름차순 정렬해주기 때문에 그대로 출력했다. (AC)