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

19699번 : 소-난다!

---

문제)

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

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

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

 

 

입력 :

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

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
vector<int> vec;
vector<bool> visited;
vector<int> ans;
 
bool check[100010];
 
// 소수 판별
bool isPrime(int a)
{
    // 1은 소수가 x
    if (a == 1) return false;
 
    // 제곱수까지 접근하며 나누어지는지 확인한다.
    for (int i = 2; i * i <= a; i++)
    {
        if (a % i == 0) return false;
    }
    return true;
}
 
void recur(int cur, int total)
{
    // 소를 m 마리 골랐을 경우
    if (cur == m)
    {
        // 소수인지 판별 + 이미 만들어진 몸무게 합인지 확인
        if (isPrime(total) && !check[total])
        {
            check[total] = 1;
            ans.push_back(total);
        }
        return;
    }
 
    // 소를 고르는 for문
    for (int i = cur; i < n; i++)
    {
        // 이미 고른 소라면 continue;
        if (visited[i]) continue;
        visited[i] = 1;
        recur(cur + 1, total + vec[i]);
        // 다음 for문을 위해 체크를 풀어준다.
        visited[i] = 0;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    
    vec.resize(n, 0);
    visited.resize(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> vec[i];
    }
    
    // 재귀를 이용하여 m마리의 소를 고른다.
    recur(0, 0);
    
    // 오름차순으로 정렬
    sort(ans.begin(), ans.end());
 
    if (ans.size() == 0)
    {
        cout << -1;
    }
    else
    {
        for (auto x : ans)
        {
            cout << x << " ";
        }
    }
 
    return 0;
 
}
 

---

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

19699번: 소-난다!