[C++] 백준 BOJ 2309 일곱 난쟁이

문제링크 : https://boj.kr/2309

무식하게 그냥 연산하면 풀리는 브루트 포스 알고리즘 문제이다.

우선 모든 값을 sum에 더하고 2개의 원소를 뽑아서 뺀 후 100이 나오면 종료한다.

생각할 수 있는 경우의 수가 적어서 단순하게 풀었다.

// BOJ 2309 일곱 난쟁이
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    vector<int> dwarf;
    int input, sum = 0;
    while (cin >> input) {
        dwarf.push_back(input);
        sum += input;
    }
 
    for (int i = 0; i < dwarf.size() - 1; i++) {
        int tmp = sum - dwarf[i];
        // 한명의 난쟁이만 빼도 100 이하면 더 이상 연산할 필요 없음
        if (tmp <= 100)
            continue;
        for (int j = i + 1; j < dwarf.size(); j++) {
            // 두 난쟁이의 합이 0이면 loop 탈출
            if (tmp - dwarf[j] == 100) {
                dwarf[i] = 0;
                dwarf[j] = 0;
                goto END;
            }
        }
    }
    END:
 
    sort(dwarf.begin(), dwarf.end());
    for (int i = 2; i < dwarf.size(); i++)
        cout << dwarf[i] << "\n";
 
    return 0;
}