# 백준 : 일곱 난쟁이(2309)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_2309_sevendwarfs)

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <cstdlib>

using namespace std;

int dwarfs[9];

void print(int v1, int v2) {
for (int i = 0; i < 9; i++) {
if ((dwarfs[i] != v1) && (dwarfs[i] != v2)) {
cout << dwarfs[i] << endl;
}
}
}

int main(void)
{

int total = 0;
int height;
for (int i = 0; i < 9; i++) {
cin >> dwarfs[i];
total += dwarfs[i];
}
sort(dwarfs, dwarfs + 9);
for (int i = 0; i < 8; i++) {
for (int j = i + 1; j < 9; j++) {
if ((total - dwarfs[i] - dwarfs[j]) == 100) {
print(dwarfs[i], dwarfs[j]);
break;
}
}
}
return 0;
}

풀이

Brute Force.. 말그대로 '다짜고짜 다 해봐서 되는게 나올때까지 가보자" 하는 무대포 방식인데.
사실 알고리즘 풀기에서 Brute Force만큼 겁나는 것은 없다. 실제 시간이 얼마나 나올지를 모르기 때문인데.. 이 문제는 대놓고 Brute Force 하라고 한다.
혹시나 DP를 이용할 수 있지는 않을까해서 여러모로 생각해봤는데. 결국 하나씩 모두 대입해봐야 하는 것 같다.
조금 더 쉽게 구하려면 총 합이 100이 되도록 하는 일곱 난장이를 구하는 것 보다는
전체 합에서 요 두명을 뺏는데 100이 나오게 하는 두명을 구하는게 더 빠를 듯 했다.
아마 기존에 주어진 갯수가 적어서 그런지 속도는 괜찮게 나온 것 같다.