[백준] 2309번 일곱 난쟁이

2309번: 일곱 난쟁이

9명 중에 순서 상관없고 중복 없이 7명을 찾아내는 것이므로 조합이다.

조합 함수를 만들어서 재귀로 풀어주면 된다.

 

결과 벡터에 있는 값 < 현재 배열에 있는 값인 경우에만

push와 카운트, sum에 더해주고 재귀호출 해주며 카운트가 7이 될 때까지 반복한다.

 

카운트가 7이고 sum이 100이면 출려해주고 끝내고

아닐 경우엔 돌아와서 pop, 카운트와 sum에서도 빼준 뒤

다음 배열의 값으로 넘어간다.

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

int cnt = 0, sum = 0, finish = 0;
vector <int> res;
void combination(int dwarf[]) {
	if (cnt == 7) {
		if (sum == 100) {
			for (int i = 0; i < 7; i++) cout << res[i] << "\n";
			finish = 1;
		}
		return;
	}
	else {
		for (int i = 0; i < 9; i++) {
			if (finish == 1) return;
			if (res.empty() || res.back() < dwarf[i]) {
				res.push_back(dwarf[i]);
				cnt++;
				sum += dwarf[i];
				combination(dwarf);
				res.pop_back();
				sum -= dwarf[i];
				cnt--;
			}
		}
	}
}

int main() {
	int dwarf[10] = { 0 };
	for (int i = 0; i < 9; i++) cin >> dwarf[i];
	sort(dwarf, dwarf + 9);
	combination(dwarf);
	return 0;
}