알고리즘 :: 백준 :: Bruteforce :: 2309 :: 일곱난쟁이

문제

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 키의 합이 100이 되는 일곱 난쟁이를 찾는 프로그램을 작성하시오. 일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

문제접근

• 9명의 난쟁이에 대해 7명을 뽑아서 키의 합을 구하고 합이 100인지를 판단하는 bruteforce 문제다.
• $_9C_7 = _9C_2 = 36$가지이므로 계산할 값은 매우 적다.
• 9명 중 7명을 뽑는 것은, 9명 중 2명을 뽑는 경우의 수와 같음을 고등학교 수학시간에 배웠다. 즉, 우리는 7명을 뽑아서 키의 합을 구하는 게 아닌, 9명의 키 합에서 2명의 키를 뺀 값이 100과 같음을 판단할 것이다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
constexpr int n = 9;
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int smallman[n];
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> smallman[i];
		sum += smallman[i];
	}								// 난쟁이 9명의 키 합을 미리 구한다.
	sort(smallman, smallman + n);	// 오름차순으로 표현해야하므로 미리 정렬한다.
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)	// 2명씩 골라서 sum에서 뺀 뒤 100과 비교한다.
			if (sum - (smallman[i] + smallman[j]) == 100) {
				for (int k = 0; k < n; ++k) {
					if (i == k || j == k) continue;
					cout << smallman[k] << '\n';
				}
				return 0;
			}
}

결과