BOJ 백준 2309 : 일곱 난쟁이

시작하면서

　이번 문제는 완전 탐색(Brute Force Search) 문제이다.

BOJ 2309 - 일곱 난쟁이

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 1가지이다.

• 아홉 난쟁이의 키

​

문제 아이디어

　난쟁이의 수가 9명이고, 이중 7명의 난쟁이 키 합이 100인 경우를 구해야한다. 경우의 수가 충분히 작으므로 모든 경우를 다 해보는 완전 탐색을 이용하면 좋다.

1. 난쟁이를 한 명씩 앞에서부터 순서대로 넣어보면서 7명까지 넣었을 때 키의 합이 100이 되는지 검사한다.
2. 100이라면 그대로 계산을 종료하고, 100이 아니라면 한 명을 빼고 다른 한 명을 넣으면서 다시 확인한다.

​

해결

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

using namespace std;

#define SEVEN_STATURE_SUM   (100)
#define SEVEN_DWARF_COUNT   (7)
#define ALL_DWARF_COUNT     (9)

bool FindSevenStature(const vector<int>& dwarfStature, vector<int>& sevenStature)
{
    if (sevenStature.size() == SEVEN_DWARF_COUNT)
    {
        int statureSum = 0;

        for (int i = 0; i < sevenStature.size(); i++)
        {
            statureSum += sevenStature[i];
        }

        if (statureSum == SEVEN_STATURE_SUM)
            return true;
        else
            return false;
    }

    for (int i = 0; i < dwarfStature.size(); i++)
    {
        vector<int>::iterator iter = find(sevenStature.begin(), sevenStature.end(), dwarfStature[i]);
        if (iter == sevenStature.end())
        {
            sevenStature.push_back(dwarfStature[i]);

            if (FindSevenStature(dwarfStature, sevenStature) == true)
                return true;
            
            sevenStature.pop_back();
        }
    }

    return false;
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<int> dwarfStature;
    vector<int> sevenStature;

    for (int i = 0; i < ALL_DWARF_COUNT; i++)
    {
        int stature;

        cin >> stature;

        dwarfStature.push_back(stature);
    }

    FindSevenStature(dwarfStature, sevenStature);

    sort(sevenStature.begin(), sevenStature.end(), less<>());

    for (int i = 0; i < sevenStature.size(); i++)
    {
        cout << sevenStature[i] << "\n";
    }

	return 0;
}

​

마치며

　자꾸 런타임 에러가 떠서 어떤 부분이 문제인가 찾아봤는데 함수 마지막 줄에 return false;를 빼먹었었다. 다음부터는 조심하자.