[C++][백준] - 일곱 난쟁이 (2309번)

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

2309번: 일곱 난쟁이

🔔 문제 : 

 

9명의 일곱난쟁이의 키가 있습니다 하지만, 여기서 진짜 난쟁이는 7명이고 2명은 가짜입니다.

 

진짜 난쟁이 7명들의 키의 합은 100이고, 여기 9명의 난쟁이중에 진짜 7명의 난쟁이를 찾아 키순으로 오름차순으로 출력하는 문제입니다.

---

🔔 Kick Point :

9명중 가짜 난쟁이 2명을 골라서 7명의 키의 합이 100인 경우를 찾아내기만 하면 됩니다.

 

우선 

1) 버블 sort 키 오름차순 정렬

2) Combination으로 2명인 경우의수 출력 후 남은 난쟁이 키 100인지 확인

3) 맞다면 출력

 

이런식으로 이어갔습니다.

 

처음에는 DFS를 어떻게 하면 쉽게 이용할 수 있을까 했는데, 짧은 코드가 생각이 안났습니다 ㅠㅠ.

 

그래서 다른사람들은 어떻게 풀지 생각하면서 찾아봤는데

알고리즘상의 sort 함수와, next_permutation를 사용하더라구요

 

sort(begin ptr, end ptr, compare(default asc))

next_permutaion(begin ptr, end ptr)

 

---

🔔 Code :

#include <iostream>
using namespace std;

int Dwraf[9];

bool cal(int a, int b) {

	int tmp = 0;
	for (int i = 0; i < 9; i++) {
		if (i == a || i == b) continue;
		tmp += Dwraf[i];
	}

	return (tmp == 100) ? true : false;
}


int main() {
	

	// 0, Input
	for (int i = 0; i < 9; i++) {
		cin >> Dwraf[i];
	}

	// 1. Bubble sort
	for (int i = 8; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (Dwraf[j] > Dwraf[j + 1]) swap(Dwraf[j], Dwraf[j + 1]);
		}
	}

	// 2. combination
	int a,b ;
	for (int i = 0; i < 8; i++) {
		for (int j = i + 1; j < 9; j++) {
			if (cal(i, j)) {
				a = i, b = j; i = 9; 
				break;
			}
		}
	}

	// 3. print
	for (int i = 0; i < 9; i++) {
		if (i == a || i == b) continue;
		cout << Dwraf[i] << endl;
	}
}

---