백준 19699 소-난다!

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

19699번: 소-난다!

---

문제

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

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

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

---

입력

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

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

---

N마리의 소가 있고, 몸무게의 합이 소수가 되도록 M마리의 소를 선별한다.

N의 범위가 그렇게 크지 않아서 , 백트래킹으로 해결 할 수 있었다.

N,M <= 9 , 1 <=  무게의 범위 <= 1000,

N이 9이고 M이 9이고 모두 무게가 1000이라면 9*1000 -> 9000이 최대 나올 수 있는 수이다.

 

9000까지 에라토스테네스의 체로 소수를 거른다음, 백트래킹으로 나올 수 있는 소수의 무게 합을 구하였다.

그리고 만들 수 있는 소수를 오름차순으로 출력해야 하므로,

C++의 map(자동으로 오름차순 정렬), (중복되는 소수 제거) 으로 만들 수 있는 소수를 넣어주었다

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int primes[9000];
int n,m;
map<int,int> Map;
map<int,int>::iterator iter;
int a[10];
int arr[10];
bool visited[10];

void init(){
    for(int i = 1;i<=9000;i++){
        primes[i] = i;
    }
    
    for(int i = 2;i<=9000;i++){
        for(int j = i+i;j<=9000;j=j+i){
            if(primes[j] == 0){
                continue;
            }
            primes[j] = 0;
        }
    }
}

void dfs(int start){
    if(start == m){
        int sum = 0;
        for(int i = 0;i<m;i++){
            sum += arr[i];
        }
        
        if(primes[sum] != 0){
            Map.insert({sum,sum});
        }
        return;
    }
    for(int i = 0;i<n;i++){
        if(visited[i] == false){
            visited[i] = true;
            arr[start] = a[i];
            dfs(start+1);
            visited[i] = false;
        }
    }
}
int main(void){
    init();
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        cin >> a[i];
    }
    
    dfs(0);
    if(Map.size() == 0){
        cout << -1;
        return 0;
    }
   
    for(iter = Map.begin();iter != Map.end();iter++){
        cout << iter->first << ' ';
    }
  
}

 

 

#include <iostream>

#include <map>

#include <algorithm>

using namespace std;

int primes[9000];

int n,m;

map<int,int> Map;

map<int,int>::iterator iter;

int a[10];

int arr[10];

bool visited[10];

void init(){

    for(int i = 1;i<=9000;i++){

        primes[i] = i;

    }

   

    for(int i = 2;i<=9000;i++){

        for(int j = i+i;j<=9000;j=j+i){

            if(primes[j] == 0){

                continue;

            }

            primes[j] = 0;

        }

    }

}

void dfs(int start){

    if(start == m){

        int sum = 0;

        for(int i = 0;i<m;i++){

            sum += arr[i];

        }

       

        if(primes[sum] != 0){

            Map.insert({sum,sum});

        }

        return;

    }

    for(int i = 0;i<n;i++){

        if(visited[i] == false){

            visited[i] = true;

            arr[start] = a[i];

            dfs(start+1);

            visited[i] = false;

        }

    }

}

int main(void){

    init();

    cin >> n >> m;

    for(int i = 0;i<n;i++){

        cin >> a[i];

    }

   

    dfs(0);

    if(Map.size() == 0){

        cout << -1;

        return 0;

    }

   

    for(iter = Map.begin();iter != Map.end();iter++){

        cout << iter->first << ' ';

    }

 

}