[백준 C++] 2309번: 일곱 난쟁이

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

 

브루트 포스 첫문제이다. 브루트 포스란 발생할 수 있는 모든 경우의 수를 무식하게 전부 탐색하는 알고리즘을 의미한다. 

 

이 문제에서는 아홉명의 난쟁이의 키를 입력 받은 뒤 오름차순으로 정렬하고 모든 경우의 수를 처음부터 검사해주었다. 

 

검사 방법은 맨 처음은 1234567을 더하여 100인지 검사하고 그뒤엔 1234568 검사하고, 1234569검사하고 아니라면 1234578검사하고 쭉 3456789까지 검사하여 주었다.

 

연산 횟수는 난쟁이에서 제외할 두명을 아홉명중에 뽑는 경우의 수 * 7이므로 9C2 *7 = 36*7 = 252밬에 연산횟수가 적다.

 

이 브루트 포스의 장점은 모든 경우의 수를 다 검사하기 때문에 무조건 정답이 나온다는 것이다. 

 

처음에 생각했던거와 달리 일단 9명의 난쟁이의 키를 모두 더하고 그중에서 두명을 뽑아 뺐을때 100이 나오는지를 검사하였다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(int argc, char* argv[])
{
	int a[10], sum = 0;
	for (int i = 0;i < 9;i++) {
		cin >> a[i];
		sum += a[i];
	}
 
	sort(a, a + 9);
 
	for (int i = 0;i < 8;i++) {
		for (int j = i + 1;j < 9;j++) {
			if (sum - a[i] - a[j] == 100) {
				for (int k = 0;k < 9;k++) {
					if (k == i || k == j) {
						continue;
					}
					cout << a[k] << '\n';
				}
				return 0;
			}
		}
	}
 
	return 0;
}

 

쉬운문제라 생각했는데 생각보다 돌아갔다.