BaekJoon 2309 일곱 난쟁이

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

소스결과 1988 KB / 0 ms

출처 Baekjoon, KOI 2004 초등부 1번

언어 C++ 17

분류 브루트 포스

 

설명

아홉 명의 난쟁이 중 일곱명을 선택해 난쟁이의 키가 100이되는 경우에 난쟁이의 키를 오름차순으로 출력하자.

 

오름차순으로 출력 하기 위해 9명의 난쟁이를 먼저 오름차순으로 정렬하자.

9명중에 7명을 조합하는 재귀 함수를 만든다.

합이 100이면 출력하자.

최종 경우에 합을 가지고만 판단하기에 앞서 누가 선태 되었는지 확인 할 수 없기에 누가 선택 됬는지 기억해줄 배열이 하나 필요하다.

 

알고리즘

1. 입력되는 9명의 난쟁이를 오름차순으로 정렬한다.

2. 9명 중 7명을 선택하는 조합 재귀함수를 만든다.

 2 - 1. 현재 선택한 난쟁이의 수가 7명이면 현재까지 선택한 난쟁이의 키 합을 구해 100이면 출력 후 종료한다.

 2 - 2. 난쟁이의 수가 7명 보다 작으면 현재 난쟁이를 선택한 경우와 선택하지 않은 경우로 나누어 재귀함수를 호출한다.

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 9;
const int TEEMO_MAX = 7;

vector<int> teemo(MAX);
bool check[MAX];

int findTeemo(int pos, int count, int sum)
{
	if (count == TEEMO_MAX)
	{
		if (sum == 100)
		{
			for (int i = 0; i < pos + 1; i++)
				if (check[i])
					cout << teemo[i] << '\n';
			return true;
		}
	}
	else
	{
		for (int i = pos; i < MAX; i++)
		{
			check[i] = true;
			if (findTeemo(i + 1, count + 1, sum + teemo[i]))
				return true;
			check[i] = false;
			if (findTeemo(i + 1, count, sum))
				return true;
		}
	}
	return false;
}

int main()
{
	for (int i = 0; i < MAX; i++)
		cin >> teemo[i];

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

	findTeemo(0, 0, 0);

	return 0;
}