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

백준의 일곱난쟁이(2309) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 문제를 간략하게 설명해보면, 9명중에 7명을 뽑아서 7명의 키의 합이 100이 되는 경우를 답으로 출력하면 되는 문제이다.

   간단한 조합문제라고 볼 수 있다.

2. 조합을 구현할 줄 안다면 쉽게 풀 수 있는 문제들이다.

   조합을 구하는 방식에 대해서 설명해보자면....

  [ 조합 구현 알아보기 ]

  [ 순열 구현 알아보기 ]

   < 위의 링크를 타고 가서 내용을 확실히 알았다면 밑에 대부분의 설명은 읽지 않아도 된다 ! >

   쉽게 5개 중에 3개를 뽑는 조합에 대해서 설명해 보겠다.

   조합은 순열과 달리, 순서과 상관이 없다.

   즉 1, 2, 3을 뽑는 것 = 1, 3, 2를 뽑는 것을 같은 것으로 취급한다.

   위의 문제도 순열이 아닌 조합문제인게, 난쟁이 1번 2번 3번의 키를 합한 것 = 난쟁이 2번 3 번 1번의 키를 합한 것은

   같기 때문에 조합 문제라는 것이다.

  

   먼저 조합에서 이미 뽑았는지 뽑지 않았는지를 판단하기 위해서 Select[] 1차원 배열이 필요하다.

   Select[a] = true 라는 것은 a번은 이미 뽑혔으니 더이상 뽑으시면 안되요 라는 의미이다.

   그럼 재귀를 통해서 조합을 구해보자.

   처음 함수는 (0, 0)으로 호출할 것이다. 여기서 매개변수 2개의 의미는

   Index와 Cnt를 의미한다. 먼저 Cnt부터 설명하자면, 지금까지 뽑은 갯수를 의미하는 것이다.

   즉, 우리는 5개 중에 3개를 뽑는 것이니, Cnt = 3 이 되면, 계산을 하면 되는것이다.

   Index는 시작점을 결정하는 변수라는 것 정도만 알면 된다.

void Combination(int Idx, int Cnt)
{
    if(Cnt == 3)
    {
        Calculate();
        return;
    }
 
    for(int i = Idx; i < 5; i++)
    {
        if(Select[i] == true) continue;
        Select[i] = true;
        Combination(i, Cnt+1);
        Select[i] = false;
    }
// 5개 중 3개를 뽑는 조합 코드
}

   조합을 구하는 코드 부분이다

   먼저 보이는 조건문부터 보자. if(Cnt == 3) 이면 Calculate()라는 함수를 통해 계산을 한다.

   위에서 말한대로, 우리가 뽑을 갯수만큼 뽑았다면, 계산을 한번 해보고 그대로 종료시키는 역할을 한다.

   핵심은 밑의 for문이다.

   반복문을 보면 for(int i = Idx; i < 5; i++) 라고 되어있다.

   Idx는 말한대로 처음에는 0이 호출되어 함수로 들어오게 될 것이다.

   그렇게 되면 for(int i = 0 ; i < 5; i++)가 실행된다.

   우리는 아직 하나도 뽑지 않았으므로, Select[] 모든 배열은 false 상태일 것이다.

   그렇다면, Select[i] = true를 통해서 0번째 공을 뽑았습니다 라고 표시를 해주고, 다시 함수를 호출하는 것이다.

   우리는, 현재 0번을 뽑았고, 전체적으로는 1개를 뽑은 상태이다.

   이 상태에서 다시 for문에 들어가보자.

   i가 0이였으므로(호출할 때 Idx값이 무슨 값으로 호출되었는지 생각해보자),

   현재 Idx값은 0일 것이다. 여기서 if(Select[i] == true) continue에 걸리게 될까?

   걸리게 될 것이다. 이전에 이미 0번을 뽑았기 때문이다. 따라서, i의 값인 그대로 증가하게 될 것이고 1이 될 것이다.

   1번은 선택하지 않았으므로, 선택할 것이고, 또 다시 재귀호출.

   이 다음에는 1번도 선택했으므로 지나가고, 2번을 선택하게 될 것이다. 또 재귀호출..

   그렇다면, 이제는 위의 if문에 걸리게 될 것이다.

   0번 1번 2번 3개를 뽑았기 때문이다 ! 이런식으로 계산이 한번 되고, 재귀가 빠지면서 Select[i] = false를 통해서

   뽑은 번호를 다시 뽑지 않았다고 표시를 해주는 식으로 반복하다보면 결국 모든 조합에 대해서 계산을 할 수 있게 된다.

   여기서 Idx는 시작점을 결정하는 것이라고 했는데, 조합을 뽑으면서

   가장 첫 시작점을 결정해 줘야 할 필요가 있다. 즉, 1 2 3 / 1 2 4 / 1 2 5 / 1 3 4 / 1 3 5 / 1 4 5 에서 시작점은 1로 동일하다.

   Idx는 이 시작점을 결정하는 역할이다. 위에 코드를 구현해보고 for문에서 i = Idx부터 시작이 아닌, 0 혹은 1, 2, 3 등으로

   값을 바꿔보고 조합 결과를 확인해본다면, Idx의 역할을 알 수 있을 것이다.

   위와 같은 방법으로 9명중에 7명을 뽑는 조합을 구현하면 된다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
 
#define endl "\n"
using namespace std;
 
int Height[9];
bool Select[9];
 
void Input()
{
    for (int i = 0; i < 9; i++)
    {
        cin >> Height[i];
    }
}
 
void Calculate()
{
    vector<int> V;
    int Sum = 0;
    cout << "선택당한 놈들 = ";
    for (int i = 0; i < 9; i++)
    {
        if (Select[i] == true)
        {
            cout << i << " ";
            Sum = Sum + Height[i];
            V.push_back(Height[i]);
        }
    }
    cout << endl;
 
    if (Sum == 100)
    {
        cout << "#############################################" << endl;
 
        sort(V.begin(), V.end());
        for (int i = 0; i < V.size(); i++)
        {
            cout << V[i] << endl;
        }
        cout << "#############################################" << endl;
 
    }
 
}
 
void Find(int Idx, int Cnt)
{
    if (Cnt == 7)
    {
        Calculate();
        return;
    }
 
    for (int i = Idx; i < 9; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Find(i, Cnt + 1);
        Select[i] = false;
    }
}
 
void Solution()
{
    Find(0, 0);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}