[백준 2309] 일곱 난쟁이

# 문제링크

www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

아홉 난쟁이 중에 일곱 난쟁이의 키를 합해서 100이 되어야 하는 문제. 이중 for문으로 9 개 중에 2개를 골라도 되고, DFS를 사용해도 된다. 

 

# 제출 코드 

// 이중 for 문 사용 코드

#include <iostream>
#include <algorithm>
# define INF 0x7f
using namespace std;

int ki[10];
int sum;

void Input() {
	for (int i = 0; i < 9; i++) {
		cin >> ki[i];
		sum += ki[i];
	}
}
void Solve() {
	for (int i = 0; i < 8; i++) {
		for (int j = i + 1; j < 9; j++) {
			if (sum - ki[i] - ki[j] == 100) {
				ki[i] = INF;
				ki[j] = INF;
				return;
			}
		}
	}
}
void Output() {
	sort(ki, ki + 9);
	for (int i = 0; i < 7; i++)
		cout << ki[i] << endl;
}
int main() {
	Input();
	Solve();
	Output();
}

 

// DFS 사용 코드 

 

#include <iostream>
#include <algorithm>
using namespace std;

int ki[10];
bool visited[10];
int sum;

void Input() {
	for (int i = 0; i < 9; i++) {
		cin >> ki[i];
		sum += ki[i];
	}
	sort(ki, ki + 9);
}
int DFS(int node, int temp) {
	if (node == 2) {
		if (sum - temp == 100) return 1;
		return 0;
	}
	for (int i = 0; i < 9; i++) {
		if (visited[i] == true) continue;
		visited[i] = true;
		if (DFS(node + 1, temp + ki[i]) == 1) return 1;
		visited[i] = false;
	}
	return 0;
}
void Output() {
	for (int i = 0; i < 9; i++)
		if(visited[i] != 1) cout << ki[i] << endl;
}
int main() {
	Input();
	DFS(0, 0);
	Output();
}