[백준 23057] 도전 숫자왕 (C++)

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

문제

---

오늘은 즐거운 축제날이다.

백남이는 축제에서 무엇을 할까 돌아다니던 중 도전 숫자왕이라는 행사를 발견했고 100만원이라는 상금에 홀려 바로 참가하였다.

도전 숫자왕은 N개의 숫자 카드를 조합하여 다양한 수를 만드는 게임이다.

이번 라운드에서는 카드의 적힌 수의 합으로 만들 수 없는 수의 개수를 외치면 이긴다.

백남이가 1등을 하여 축제를 즐길 수 있도록 도와주자.

입력

---

첫 번째 줄에는 카드의 개수 N(1 ≤ N ≤ 20)이 주어진다.

두 번째 줄에는 N개의 수가 주어진다.

입력으로 주어지는 수는 100,000,000 이하의 자연수이다.

 

출력

---

모든 카드에 적힌 수의 합을 M이라고 할 때, 1 이상 M이하의 자연수 중 만들 수 없는 수의 개수를 출력한다.

 

문제 풀이

---

브루트포스 문제.

 

가능한 모든 수를 구하는 문제이므로 브루트포스 문제이다. 만들 수 있는 수를 구한 다음 set에 저장한 후, M에서 set의 개수만큼 빼주면 된다.

 

함수를 만들고, 합할 수의 개수를 인자로 정한다. 빠른 탐색을 위해 같은 조합은 탐색하지 않도록 인덱스 역시 인자로 넣고, 현재 합을 저장할 변수도 만들어준다. depth가 합할 수의 개수만큼 도달하면 그 수의 개수만큼 합한 것이고, 따라서 set에 넣어주면 된다. depth가 그보다 작다면 합할 수를 탐색해준다. 이미 선택하지 않은 수에 대해 선택하여 더한 후 재귀적으로 함수를 호출하여 depth를 증가시킨다.

 

아래는 코드.

#include <iostream>
#include <set>
using namespace std;
int N;
int* arr;
bool* isUsed;
set<int> s;

void find(int currentDepth, int maxDepth, int index, int currentSum)
{
	if (currentDepth == maxDepth)
	{
		s.insert(currentSum);
	}
	else
	{
		for (int i = index; i < N; i++)
		{
			if (isUsed[i] == false)
			{
				isUsed[i] = true;
				find(currentDepth + 1, maxDepth, i + 1, currentSum + arr[i]);
				isUsed[i] = false;
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;
	arr = new int[N];
	isUsed = new bool[N];
	int M = 0;
	for (int i = 0; i < N; i++)
	{
		isUsed[i] = false;
		cin >> arr[i];
		M += arr[i];
	}
	for (int i = 0; i < N; i++)
	{
		find(i, N, 0, 0);
	}
	int count = s.size();
	cout << M - count << "\n";
	return 0;
}