[알고리즘 문제] 백준2309 - 일곱 난쟁이

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

2309번: 일곱 난쟁이

 

서로다른 n개 에서 r개를 뽑았을 때 r개의 숫자들의 합이 100이 이면 r개를 출력하는 문제입니다. 이 문제는 재귀를 사용하였습니다.

 

search함수의 for문에서 arr에 있는 값들을 하나씩 temp에 넣으면서 temp의 길이가 7이될때 temp의 원소들의 합이 100이 되는지 검사합니다. 여기서 난쟁이들이 중복되어 들어가는 것을 허용하지 않기 때문에 visited를 사용하여 이미 사용한 난쟁이를 체크해 주었습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> temp;
vector<int> arr(9);
int visited[9];
bool isFind = false;

bool sumCheck()
{
    int sum = 0;
    for (int i = 0; i < temp.size(); i++)
    {
        sum += temp[i];
    }
    if (sum == 100)
    {
        return true;
    }
    return false;
}

void search()
{
    if (isFind)
    {
        return;
    }
    if (temp.size() == 7)
    {
        if (sumCheck())
        {
            isFind = true;
            sort(temp.begin(), temp.end());
            for (int i = 0; i < temp.size(); i++)
            {
                cout << temp[i] << "\n";
            }
        }
        return;
    }

    for (int i = 0; i < arr.size(); i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            temp.push_back(arr[i]);
            search();
            visited[i] = false;
            temp.pop_back();
        }
    }
}

int main()
{

    for (int i = 0; i < 9; i++)
    {
        cin >> arr[i];
    }
    search();
    return 0;
}