[백준] 3040번: 백설 공주와 일곱 난쟁이 - 완전 탐색 (Brute Force)

1. Brute Force

• 정의
  • 완전 탐색 기법 중 하나로, 반복문, 조건문을 통해 문제를 해결하는 기법
• 예시 - 3040번: 백설 공주와 일곱 난쟁이

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

3040번: 백설 공주와 일곱 난쟁이

• 풀이
  • 아홉 난쟁이 중 일곱난쟁이의 합은 100을 다르게 생각해보면,  아홉 난쟁이 중 두 가짜 난쟁이를 선택한 경우 찾기 => 9C2
  • 아홉 난쟁이의 합에서 100를 빼면, 두 가짜 난쟁이의 합이 나옴
  • 이를 토대로, 입력받은 난쟁이를 이중 for문으로 조합하여 가짜 난쟁이의 합이 나오는 경우를 찾아 제외하여 출력

• 코드

#include<iostream>
using namespace std;

int main() {

	int array[9];
	int total_dwarf = 0; // 아홉난쟁이의 모든 숫자를 더한 값
	for (int i = 0; i < 9; i++) cin >> array[i];
	for (auto arr : array)  total_dwarf += arr;

	int Non_dwarf = total_dwarf - 100; // 아홉난쟁이 중 가짜 난쟁이 둘의 합
	
	// 난쟁이 둘의 합이 Non_dwarf가 되는 경우 찾기
	for (int i = 0; i < 9; i++)
		for (int j = i + 1; j < 9; j++)
			if (array[i] + array[j] == Non_dwarf)
				for (auto arr : array)
					if (array[i] != arr && array[j] != arr)
						cout << arr << "\n";
}