[BOJ] 소-난다! 19699번 C++

 

 

문제

지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 하늘을 날 수 있다는 사실을 깨달았다. 이 사실이 퍼지자 소들은 다시 자유롭게 하늘을 날기 시작했다.

소들이 하늘을 날며 우(牛)통사고가 빈번해지자, 농부 존은 소들이 하늘을 나는 것에 제한을 두었다. 소들은 항의했지만 소들의 항의는 받아들여지지 않았다.

농장에는 N$N$마리의 소가 있다. 농부 존은 소들의 몸무게의 합이 소수(prime)가 되도록 M$M$마리의 소를 선별할 계획이다. 농부 존의 계획에 맞게 소를 선별했을 때 나올 수 있는 몸무게의 합을 모두 출력하시오.

입력

첫째 줄에 농장에 있는 소들의 수 N$N$, 선별할 소의 수 M$M$이 주어진다.

둘째 줄에 소들의 몸무게 Hi$H_i$가 주어진다.

출력

 M마리 소들의 몸무게 합으로 만들 수 있는 모든 소수를 오름차순으로 출력한다. 만약 그러한 경우가 없다면 −1을 출력한다.

 

 

접근 방식

먼저 소수인 값들을 '에라토스테네스의 체' 알고리즘을 사용해 미리 구한 후

농장들의 수를 M개 선택해 몸무게의 합이 소수인지 확인할 수 있도록 구하였다.

이때 주의할 점은 만들 수 있는 모든 소수가 중복으로 나올 수 있어서

set 자료구조를 사용했다

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int N,M;
bool isPrime[2000001], visited[13];
vector<int> weights;
set<int> ans;

void sol(int cnt,int total) {
    if(cnt == M) {
        if(isPrime[total]) ans.insert(total);
        return;
    }

    for(int i=0; i<N; i++) {
        if(visited[i]) continue;
        visited[i] = true;
        sol(cnt+1, total + weights[i]);
        visited[i] = false;
    }

}


int main() {
    cin>>N>>M;
    weights.resize(N);

    for(int i=0; i<N; i++) cin>>weights[i];

    memset(isPrime, true, sizeof(isPrime));
    memset(visited, false, sizeof(visited));

    isPrime[0] = isPrime[1] = false;

    for(int i=2; i*i<=100000; i++) {
        if(isPrime[i]) {
            for(int j=i*i; j<=1000000; j+= i) {
                isPrime[j] = false;
            }
        }
    }

    sol(0, 0);
    if(ans.empty()) {
        cout<<-1;
        return 0;
    }
    for(auto a : ans) cout<<a<<" ";
}