[백준] 19699: 소-난다!

문제 링크

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

접근 방식 / 풀이

M마리의 소를 N개 골라, 해당 수가 소수인 것만 모아 출력하는 문제이다.
따라서, $_{M}\mathrm{C}_{N}$을 수행하는 법을 알아야 하고, 소수 판별법을 알아야 해당 문제를 풀 수 있다.

next_combination ?

C++의 <algorithm> 헤더에서는 next_permutation 이라는 함수를 제공한다. 함수의 인자로 벡터 혹은 배열을 넣으면, 해당 벡터 혹은 배열의 다음 순열을 만들어주는 함수이다. (return : 다음 배열이 있으면 참, 없으면 거짓을 리턴한다)

하지만 next_combination이라는 함수는 존재하지 않는데, 우리는 next_permutaion을 통해 이를 구현해낼 수 있다.

어떤 수를 고를 지를 next_permutation을 통해 알아내자!

예를 들어, 4개의 수에서 2개를 고른다고 하자.
이 때 {0, 0, 1, 1}이라는 배열을 만들고, next_permutation 함수를 통해 이들로 만들어질 수 있는 모든 순열을 만든다면 ?

{0, 0, 1, 1}
{0, 1, 0, 1}
{0, 1, 1, 0}
{1, 0, 0, 1}
{1, 0, 1, 0}
{1, 1, 0, 0}

아래와 같은 결과가 나온다.
이 네 가지 수가 다 다른 값을 가진다면, $4!$으로 총 24가지 값이 나올 테지만, 중복되는 경우를 제외하고 리턴하기 때문에

총 6가지의 결과가 나오게 되고, 이것은 곧 $_{4}\mathrm{C}_{2}$의 계산 결과와 같으며, 위 배열에서 1의 값을 가지는 인덱스의 값을 빼내온다면

arr[2], arr[3]
arr[1], arr[3]
arr[1], arr[2]
arr[0], arr[3]
arr[0], arr[2]
arr[0], arr[1]

우리가 원하는 $_{4}\mathrm{C}_{2}$의 조합을 얻을 수 있다.

소수 판별법

2에서부터 $\sqrt{N}$ 까지의 정수 중에서 $N$을 나눌 수 있는 수가 있다면 그 수는 소수가 아니다. $\sqrt{N}$ 까지만 연산을 수행해도 되는 이유는 조금만 생각해보면 알 수 있다.

소수가 아닌 수는 최소한 1과 자신이 아닌 2개 이상의 수들의 곱으로 이루어져 있다. 이 수는 같은 수일수도 있고(제곱 꼴), 아닐 수도 있다.

1. 같은 수의 곱으로 이루어져 있는 경우
   예 ) $25 = 5 \times 5$
2. 다른 수의 곱으로 이루어져 있는 경우
   예 ) $35 = 5 \times 7$

( 1 ) 의 경우를 보자. $\sqrt{25} = 5$이고, $2$에서 $\sqrt{25}$ 까지 연산을 수행하게 되면, $5$에서 $25\,\bmod\,5 == 0$ 이기에 이 수는 소수가 아님이 판별된다.

( 2 ) 의 경우도 마찬가지이다. $\sqrt{35} = 5.916..$이고, $2$에서 $\sqrt{35}$ 까지 연산을 수행하게 되면, $5$에서 $35\,\bmod\,5 = 0$ 이기에 이 수는 소수가 아님이 판별된다.


즉, 소수가 아닌 어떤 수는 $\sqrt{N}$의 값보다 같거나 작은 어느 정수로 인해 나눠질 수 있다.
( 2 ) 에서 $35$의 약수 $5$가 밝혀졌다면, $\sqrt{35}$ 이상의 어떤 정수 중에서도 $35$의 약수가 있다는 것은 자명한 사실이라는 것이다.

위 두 가지 배경 지식을 가지고 있다면, 손쉽게 풀 수 있을 것이다. :)

---

답안 코드 링크 (Github)

Github Solution Link

정답 코드

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

void	fastio(void);
int	isprime(int x);

int main(void)
{
	int		num[10];
	int		n, m, tot, tmp;
	vector<int>	comb;
	set<int> ret;

	fastio();
	cin >> m >> n;
	for (int i = 0; i < m; i++)
	{
		cin >> tmp;
		num[i] = tmp;
		if (i < n)
			comb.push_back(1);
		else
			comb.push_back(0);
	}
	sort(comb.begin(), comb.end());
	do {
		tot = 0;
		for (int i = 0; i < m; i++)
		{
			if (comb[i])
				tot += num[i];
		}
		if (tot < 2 || (tot > 2 && tot % 2 == 0))
			continue;
		if (isprime(tot))
			ret.insert(tot);
	} while (next_permutation(comb.begin(), comb.end()));
	if (ret.size() == 0)
	{	cout << "-1\n";	return (0);	}
	for (auto i = ret.begin(); i != ret.end();)
	{
		cout << *i;
		if (++i != ret.end())
			cout << " ";
	}
	cout << "\n";
	return (0);
}

int	isprime(int x)
{
	for (int i = 3; i <= (int)sqrt(x); i++)
	{
		if (x % i == 0)
			return (0);
	}
	return (1);
}

void	fastio(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}