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

 

 

<코드>

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

int N, R, H[9];
int cow[9000];
int check[9];

bool isPrimeNum(int x) // 에라토스테네스의 체 (소수판별)
{
	int flag = true;

	for (int i = 2; i * i <= x; i++)
	{
		if (x % i == 0)
		{
			flag = false;
			break;
		}
	}
	if (flag) return true;
	else return false;
}

void DFS(int s, int L) // DFS를 통한 조합구하기
{
	if (L == R)
	{
		int sum = 0;
		for (int i = 0; i < R; i++)
		{
			sum += H[check[i]];
		}	
		if (isPrimeNum(sum)) cow[sum] = 1;	
	}
	else
	{
		for (int i = s; i < N; i++)
		{
			check[L] = i;
			DFS(i + 1, L + 1);
		}
	}
}

int main()
{
	cin >> N >> R;

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

	DFS(0, 0);

	int flag = true;
	for (int i = 0; i < 9000; i++)
	{

		if (cow[i] == 1)
		{
			cout << i << " ";
			flag = false;
		}
	}
	if (flag == true)
	{
		cout << -1;
	}

}

 

풀이 방법

DFS로 조합을 구하고 에라토스테네스의 체를 통해서 소수를 판별하고 소수들을 출력하였다.

 

 

더 알아보기

cocoon1787.tistory.com/81?category=831130

[ C/C++] 순열(Permutation)과 조합(Combination) 알고리즘 구현하기

cocoon1787.tistory.com/88?category=831130

[C/C++] 소수 구하기 (for문, 재귀, 에라토스테네스의 체)

 

 

 

 

 

 

 

www.acmicpc.net/problem/19699

19699번: 소-난다!