[백준/BOJ] 백준 2309번 : 일곱 난쟁이

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

2309번: 일곱 난쟁이

완전탐색(브루트포스)을 이용해 난쟁이가 아닐것 같은 후보 2명을 뽑아서 정말 난쟁이가 아닌지 확인한다.

확인 방법은 전체 합에서 난쟁이가 아닐것 같은 후보 2명의 합을 빼서 판단한다.

2명을 뽑는 조합이므로 중복된 조합이 나타나지 않게 하였다.

 

코드

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

int sum = 0;

//일곱 난쟁이가 아닌 사람을 찾는다
bool check(vector<bool> notseven, vector<int> human)
{
	int tempsum = 0;

	for (int i = 0; i < 9; i++)
	{
		if (notseven[i])
			tempsum += human[i];
	}
	//전체 합에서 어떤 2명의 합을 뺏는데 100이라면
	//그 2은 난쟁이가 아니다.
	if (sum - tempsum == 100)
		return true;
	else
		return false;
}

vector<int> solve(vector<bool> notseven,vector<int> human, int first, int num)
{
	vector<int> ret;

	//난쟁이가 아닌 후보 2명을 뽑았을때
	if (num == 2)
	{
		//그 2명이 정말 난쟁이가 아니라면
		if (check(notseven, human))
		{
			for (int i = 0; i < 9; i++)
			{
				if (notseven[i] == false)
					ret.push_back(human[i]);
			}
			//진짜 난쟁이들을 반환
			return ret;
		}

		else
		{
			//아니라면 빈 벡터를 반환
			return ret;
		}
	}

	else
	{
		//완전 탐색을 진행해 난쟁이가 아닐것 같은
		//2명을 뽑는다.
		for (int i = 0; i < human.size(); i++)
		{
			if (i > first)
			{
				notseven[i] = true;
				ret = solve(notseven, human, i, num + 1);
				
				//진짜 난쟁이들이 들어왔다면
				if (ret.empty() == false)
				{
					return ret;
				}
				notseven[i] = false;
			}
		}
	}

	return ret;
}
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	vector<int> human;
	vector<int> sevenhuman;
	vector<bool> notseven(9, false);

	int temp;

	for (int i = 0; i < 9; i++)
	{
		cin >> temp;
		sum += temp;
		human.push_back(temp); //9명의 키를 입력받는다.
	}

	//진짜 난쟁이들을 구한다.
	sevenhuman = solve(notseven, human, -1, 0);

	sort(sevenhuman.begin(), sevenhuman.end());

	for (int i = 0; i < 7; i++)
	{
		cout << sevenhuman[i] << "\n";
	}


	return 0;
}