[PS 백준 - 2.1] 2309번: 일곱 난쟁이

문제 정보

백준 2309번 - 바로가기

• 난이도: 브론즈 2
• 알고리즘: 브루트포스 알고리즘

---

코멘트

먼저 입력받은 9명의 키를 정렬하고, $_{9}\mathrm{C}_{7}$ 씩 골라서 모든 경우를 탐색하면 된다. 7명이 골라졌을 때마다 키의 합을 매번 구해서 합이 100이면 해당 경우의 키들을 출력한다.

---

소스 코드

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

using namespace std;

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

	vector<int> vec;
	int n;
	for (int i = 0; i < 9; i++) {
		cin >> n;
		vec.push_back(n);
	}

	sort(vec.begin(), vec.end());
	
	// 9C7번 모두 완전 탐색하면 된다!
	int sum = 0;
	int ansI = 0, ansJ = 0;

	for (int i = 0; i < 9; i++) {
		for (int j = i+1; j < 9; j++) {
			for (int k = 0; k < 9; k++) { 
				if (k != i && k != j) {
					sum += vec[k];
				}
			}
			if (sum == 100) {
				ansI = i;
				ansJ = j;
				break;
			}
			else sum = 0;
		}
		if (sum == 100) break;
		else sum = 0;
	}
	
	for (int k = 0; k < 9; k++) {
		if (k != ansI && k != ansJ) {
			cout << vec[k] << "\n";
		}
	}
}