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

문제링크 : https://www.acmicpc.net/problem/19699

19699번: 소-난다!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[9];
bool check[9000];
set<int>s;
int N, M;

void func(int cnt, int idx, int sum)
{
    if(cnt == M) //선별할 숫자와 같으면
    {
        if(check[sum]) s.insert(sum); //소수면 포함
        return;
    }

    for(int i = idx; i<N; i++)
    {
        func(cnt+1, i+1, sum+arr[i]); //하나씩 더해가며 체크
    }
}

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

    cin >> N >> M;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    memset(check, true, sizeof(check));
    check[0] = check[1] = false; //0과 1은 소수아님
    for(int i=2; i<=sqrt(9000); i++)
    {
        for(int j = i*2; j<=9000; j+=i) //해당 값의 배수 체크
        {
            check[j] = false;
        }
    }

    func(0, 0, 0);

    for(auto i : s) cout << i << " ";
    if(s.empty()) cout << -1;

    return 0;
}

소수판별을 이용한 문제이다.

처음에 소의 몸무게를 입력받고 바로 최대값인 9000까지의 소수를 먼저 체크하고 시작했다.

 

그 다음으로 재귀함수를 돌리는데 카운트, 현재 인덱스, 현재 합을 넘겨주어 하나씩 더해가며 카운트가 선별할 숫자와 같아지면 현재 합이 소수인지 아닌지 체크하도록 하였다.

이때 중복값이 생길 수 있어서 소수인 값들은 set으로 넣도록 하였다.

 

2 4 10 (합 : 16)
2 4 5 (합 : 11)
2 4 8 (합 : 14)
2 10 5 (합 : 17)
2 10 8 (합 : 20)
2 5 8 (합 : 15)

4 10 5 (합 : 19)
4 10 8 (합 : 22)
4 5 8 (합 : 17)

10 5 8 (합: 23)

위에서 소수는 11, 17, 19, 23