백준 2309번(완전 탐색)

백준 2309번(완전 탐색)

이 문제는 2가지 방법으로 해결할 수 있었습니다. 첫번째로 순열을 이용해서 해결할 수 있습니다. 9명 중 7명을 뽑고 sum이 100이면 출력하는 방식입니다.

// 순열 응용
vector<int> p(2);
vector<int> seq;

int main() {
	int num;
	int sum;

	for (int i = 0; i < 9; i++) {
		cin >> num;
		seq.push_back(num);
		if (i < 7) {
			p.push_back(1);
		}
	}

	sort(seq.begin(), seq.end());

	do {
		sum = 0;

		for (int i = 0; i < 9; i++) {
			if (p[i]) {
				sum += seq[i];
			}
		}

		if (sum == 100) {
			for (int i = 0; i < 9; i++) {
				if (p[i]) {
					cout << seq[i] << endl;
				}
			}
			return 0;
		}
	
	} while (next_permutation(p.begin(), p.end()));

	return 0;
}

두 번째 방법은 발상을 바꿔서 생각할 수 있었습니다. sum이 100인 7명을 뽑는 다는 것은 7명의 sum이 100이 되게 나머지 2명을 뽑는 다는 것과 같은 말입니다. 이런 방식으로 생각할 경우 for를 중첩하여 더욱 간단하게 해결할 수 있습니다.

// 역발상 for문으로 해결
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> seq;

int main() {
	int sum = 0;
	int num;

	for (int i = 0; i < 9; i++) {
		cin >> num;
		seq.push_back(num);
		sum += num;
	}
	
	sort(seq.begin(), seq.end());

	for (int i = 0; i < 8; i++) {
		for (int j = i + 1; j < 9; j++) {
			if (sum - seq[i] - seq[j] == 100) {
				for (int k = 0; k < 9; k++) {
					if (k != i && k != j) {
						cout << seq[k] << endl;
					}
				}

				return 0;
			}
		}
	}

	return 0;
}