[브루트포스] BOJ 2309 일곱 난쟁이 - 오답노트

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

2309번: 일곱 난쟁이

- 문제 파악

9명의 난쟁이들 키중에서 7명의 키의 합이 100임을 이용한다.

 

- 나의 시도

9명의 모든 경우의 수를 살피면서 100 - (경우의 수 합) = 0 임을 이용하려고 했으나 너무 복잡하게 접근

 

- 정답

9명 모두의 합중에서 2명의 키만 빼면 100이 됨을 이용, 나의 시도와 비슷하지만

nCk = nCn-k 임을 이용해서 문제를 더 간단하게 만들었다.

 

#include "bits/stdc++.h"

using namespace std;

int arr[10];

int main()
{
    int n = 9;
    int k = 0;
    int nNan = 0;
    while (n--)
    {
        cin >> arr[k];
        nNan += arr[k];
        k++;
    }

    sort(arr, arr + 9);

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (nNan - (arr[i] + arr[j]) == 100)
            {
                for (int q = 0; q < 9; q++)
                {
                    if (q == i || q == j)
                        continue;

                    cout << arr[q] << "\n";

                }

                return 0;
            }
        }
    }

}