일곱 난쟁이 (feat. 백준, 2309번)

일곱 난쟁이
https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
int arr[9], ans[7];
bool done, visit[9];
void dfs(register int idx, register int count) {
	if (count == 7) {
		if (accumulate(ans, ans + 7, 0) == 100)
			done = true;
		return;
	}
	for(register int i = idx; i < 9; ++i)
		if (!visit[i]) {
			visit[i] = true;
			ans[count] = arr[i];
			dfs(i + 1, count + 1);
			if (done)
				return;
			visit[i] = false;
			ans[count] = 0;
		}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	done = false;
	for (register int i = 0; i < 9; ++i)
		cin >> arr[i], visit[i] = false;
	dfs(0, 0);
	sort(ans, ans + 7);
	for (register int i = 0; i < 7; ++i)
		cout << ans[i] << "\n";
	return 0;
}
// *&)*@*

 

 

1. 9개에 대해 7개를 선택할 수 있는 조합을 구합니다.
2. 각 조합들의 합이 100이 되는 경우, 종료 후 정렬하여 출력합니다.