[Brute Force] BOJ 2309 번 : 일곱 난쟁이

문제

---

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

 

입력

---

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

 

문제 요약

---

9명의 키가 모두 다른 난쟁이들이 있다. 이 중에서 키의 합이 100이 되도록 7명을 고르는 문제.

 

풀이

---

출처 : https://www.biaf.or.kr:47436/mobile/2017/programs_view.php?idx=58&m_idx=153

문제를 읽어보니 우리는 7명의 난쟁이를 골라야합니다.

보통 특정한 배열의 번호를 하나씩 골라서 돌아볼 때 보통 하나의 for 문을 사용합니다.

그렇다면 우리는 7개의 for 문을 돌아야 하나?!

 

상당히 비효율적이기 때문에 문제를 다르게 생각해봅시다.

9명 중 7명을 고르는 경우의 수를 구해보면 9C2 = 9*7 / 2*1 = 36 이라는 계산이 나옵니다.

 

중등 수학에서 나오는 경우의 수를 되새겨보시면...

우리는 9C7 = 9C2가 같다는 걸 알 수 있습니다.

 

이건 9명 중에서 7명을 고르는 것은 

9명중 2명을 고르는 것과 같다는 의미입니다.

 

이렇게 되면 우리는 두 개의 for 문 만으로 문제를 해결할 수 있게 됩니다.

하지만 두 개를 선택함에도 불구하고 우리는 7개의 값을 출력해야 하기 때문에

하나의 for문을 더 사용해야 합니다.

 

하지만 정답을 출력해주는 for문은 보시는 것처럼 

답을 발견했을 때 딱 한 번만 수행을 하기 때문에 전체적인 시간 복잡도는 O(N^2) 이라고 할 수 있습니다.

 

 

 

 

 

 

코드

---

#include <iostream>
#include <algorithm>
#define PEOPLE 9 //9명의 난쟁이

using namespace std;

int main() {

	int array[PEOPLE]; //난쟁이의 키를 입력받는다.
	int sum = 0; // 모든 난쟁이의 키 총합
	for (int i = 0; i < PEOPLE; i++) {
		cin >> array[i];
		sum += array[i];
	}
	sort(array, array + PEOPLE); //키순으로 정렬

	for (int i = 0; i < PEOPLE; i++) { // 첫번째 난쟁이 선택
		for (int j = i + 1; j < PEOPLE; j++) { // 두번째 난쟁이 선택
			if (sum - array[i] - array[j] == 100) {
				for (int k = 0; k < PEOPLE; k++) {
					if (k == i || k == j) continue;
					// 선택된 두 난쟁이는 제외
					cout << array[k] << '\n';
					
				}
				return 0; // 시스템을 종료한다.
			}
		}
	}

	return 0;
}