이때, 경우의 수를 다 해보는데까지 걸리는 시간이 문제의 시간제한을 넘지 않아야 한다.
부루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 * 방법 1개를 시도해보는 데 걸리는 시간 복잡도)가 걸린다.
https://www.acmicpc.net/problem/2309

아홉명의 난쟁이 중 일곱명의 난쟁이를 찾는 문제이다.
아홉명 중 일곱명을 고르는것은, 아홉명 중 두명을 고르는 것과 같다!
가지
그럼, 나머지 난쟁이의 키의 합을 고르는 시간 복잡도는 이다.
따라서, 이 문제는 으로 해결할 수 있다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
vector<int> v;
// 총 숫자 합.
int sum = 0;
for(int i = 0; i < 9; i++){
int a;
cin >> a;
sum += a;
v.push_back(a);
}
// 오름차순으로 정렬
sort(v.begin(), v.end());
// 2중 for문 설계.
for(int i = 0; i < v.size() -1; i++){
for(int j = i + 1; j < v.size(); j++){
// 두 수를 뻇는데 100이 된다면, v[i]와 v[j] 는 빠져야할 숫자.
if(sum - (v[i] + v[j]) == 100){
// v[i]와 v[j]를 제외하고 싹다 출력.
for(int k = 0; k < v.size(); k++){
if(k != i && k != j){
cout << v[k] << endl;
}
}
// 프로그램 종료.
return 0;
}
}
}
return 0;
}
조금 실수가 있었던 부분이 있는데, 출력 후에, return 0;를 호출해 프로그램을 종료하는 부분이다.

return 0;를 추가하지 않아서 2번의 실패가 있었다..
만약 return 0;를 추가하지 않으면, 프로그램이 모든 경우를 확인한 후에도 계속 실행되는데 이유가 있었던 것 같다. (그런데, 문제를 읽어보면 그대로 실행되도 큰 문제 없지 않나,,?)