2309 문제 일곱 난쟁이문제 풀이
깊이 우선탐색처럼보이지만 다른 방법으로도 쉽게 풀수 있다.
조합을 이용하는 것이다.
가짜를 뽑는경우의 수를보면 9c2이니 총 가지의수는 (9*8)/(2*1) 이 나오게 된다.
여기서 중요할점은 가짜를 제외하고 뽑을경우 총합이 100이 되면 가짜가 자동으로 나오게된다.
아래는 그 코드이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
vector<int> arr;
arr.resize(9);
for (auto &i : arr) {
cin >> i;
}
for (int i = 0; i < arr.size()–1; ++i) {
for (int j = i+1; j < arr.size(); ++j) {
int sum = 0;
for (int k = 0; k < arr.size(); ++k) {
if (k == i || k == j) continue;
sum += arr[k];
}
if (sum == 100) {
int val[2]{ arr[i],arr[j] };
for (auto &i : val) {
arr.erase(std::find_if(arr.begin(), arr.end(),
[&](int a) {return a == i; })
);
}
goto ONE;
}
}
}
ONE:
std::sort(arr.begin(), arr.end());
for (auto &i : arr) {
std::cout << i << std::endl;;
}
}
|
cs |