백준 2309번 일곱 난쟁이

백준 문제 : https://www.acmicpc.net/problem/2309

참고 : https://blockdmask.tistory.com/163

/**************************************************************************/
//#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <unordered_map>
#include <stack>
 
using namespace std;
 
 
 
/***********************백준 2309번 일곱 난쟁이*********************************/
// https://www.acmicpc.net/problem/2309
 
vector<int> input;
 
int getSum()
{
    // 전체 난쟁이들의 키의 합
    int iNum = 0;
    for (size_t i=0; i< input.size(); i++)
    {
        iNum += input[i];
    }
    return iNum;
}
 
int main() 
{
 
    // 제출용
    input = vector<int>(9, 0);
    for (int i = 0; i < 9; i++)
        scanf("%d", &input[i]);
 
    //input.push_back(20);
    //input.push_back(7);
    //input.push_back(23);
    //input.push_back(19);
    //input.push_back(10);
    //input.push_back(8);
    //input.push_back(13);
    //input.push_back(15);
    //input.push_back(25);
 
    int iTotalNum = getSum();
    bool bIs = false;
    for (int i = 0; i < 8; i++)
    {
        for (int j = i+1; j < 9; j++)
        {
            int iNum = iTotalNum - (input[i] + input[j]);
            if (iNum == 100)
            {
                input[i] = -1;
                input[j] = -2;
                bIs = true;
                break;
            }
        }
        if (bIs)
        {
            break;
        }
    }
 
    std::sort(input.begin(), input.end());
 
    for (int i = 2; i < 9; i++)
        printf("%d\n", input[i]);
 
    return 0;
}

아홉명의 난쟁이 중 

일곱명의 난쟁이 키를 더했을때 100 이어야 하니까.

아홉명의 난쟁이 들의 키 - (특정 두명의 키) = 100

인 2가지의 경우를 찾는 방법으로 문제를 해결

int iNum = iTotalNum - (input[i] + input[j]);

만약에 7명의 난쟁이의 키 합이 100인경우로 문제 해결을 할려면

7가지의 경우를 찾는 방법으로...

for (int i = 0; i < 8; i++)
        for (int j = i + 1; j < 9; j++)
            for (int k = j + 1; k < 9; k++)
                for (int y = k + 1; y < 9; y++)
                    ...
                    int iNum = (input[i] + input[j] + input[k] + input[y]...);
                    if (iNum == 100)

7가지의 경우를 찾는 방법은 코드도 많이지고 반복도 많다. 비효율 적인방법

어떤 복수의 경우를 생각할때는 반대로 생각 하는 방법을 찾도록 해보자