[ 백준 6603 ] 로또 (C++)

백준의 로또(6603) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 입력으로 주어지는 숫자들 중에서 6개를 뽑아서 만들 수 있는 모든 경우를 출력시키는 문제이다.

- 조합을 구하는 문제이며, DFS를 이용해서 구할 수 있는 문제이다.

[ 문제풀이 ]

1) 먼저 주어지는 숫자들을 저장할 배열 MAP[]을 사용해서 저장한다.

2) 숫자의 전체 갯수 중에서 6개를 뽑는 경우를 모두 출력시키면 되는데, 순서가 상관없기 때문에 조합을 구하면 되는 것이다.

   - (1,2,3,4,5,6,7) 중에서 (1,2,3,4,5,6)을 뽑으나 (3,2,1,6,5,4)를 뽑으나 같은 경우로 취급 = 조합

   또한 중복해서 뽑을 수 없기 때문에 중복조합이 아닌 일반 조합이다.

3) 조합을 구현하기 위한, Visit배열을 하나 선언하다. Visit배열을 통해서 그 값이 선택됬는지, 안됬는지를 판단할 것이다.

4) 지금부터는 밑의 소스코드를 참고하면서 읽으면 더 쉬울 것이다.

   조합을 구할 하나의 함수(Select(int Idx, int Cnt)) 를 만드는데, 여기서 매개변수 2개의 의미를 생각하면서 코드를 구현하면

   보다 쉬울 것이다. 

   첫 번째 매개변수인 Idx는 Index번호를 의미하며, 이 함수에서 하는 역할은, 시작점을 결정하는 역할을 한다.

   예를 들어서, 처음 호출 할 때인 Idx = 0인 경우를 보면, Select()함수에서는 반복문을 0 ~ K까지 실행시킨다.

   카드를 3장 뽑는다고 가정했을 때, 0 1 2 / 0 1 3 / 0 1 4와 같이... 시작점이 0으로 동일한 경우가 있다. 이러한 시작점을

   선택해주는 역할이며, for(int i = Idx ~~)이 구문에서 Idx를 숫자 0혹은 1, 2, 3등을 직접 넣어본다면 어떻게 결과가 바뀌는지

   직접 확인해 볼 수 있을 것이다.

   두 번째 매개변수인 Cnt는 최종 계산을 위한 변수이다. 숫자를 하나 선택할 때마다 Cnt의 값이 증가시킬 것이고 문제에서

   요구하는 대로 6개를 뽑는다면, 즉 Cnt 값이 6이 된다면 더 이상 숫자를 뽑는 곳으로 가는 것이 아닌, 뽑은 숫자들을

   출력시킬 것이다.

5) 조합 부분에 대해 구체적으로 설명해 보자면, 4)에서 말했다 시피, for(int i = Idx ~ K; i++) 라는 반복문에서 조합을 결정

   한다. 선택된 숫자들에 대해서는 Visit[i] 값을 true로 바꿔주고, 이미 true인 숫자에 대해서는 그냥 지나쳐버리는 과정을

   반복한다. 동시에 선택된 숫자들은 Vector에 넣어주고, 출력 시, 이 Vector를 통해서 출력시킨다.

   이후, 모든 조합에 대해 계산을 하기 위해서 true였던 값을 빼주면서 동시에 vector에서도 값을 빼주는 연산을 해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
 
#define endl "\n"
#define MAX 13
using namespace std;
 
int K, Select_Num;
int MAP[MAX];
bool Visit[MAX];
 
vector<int> V;
 
void Initialize()
{
    V.clear();
    Select_Num = 6;
    memset(MAP, 0, sizeof(MAP));
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    for (int i = 0; i < K; i++)
    {
        cin >> MAP[i];
    }
}
 
void Print_Number()
{
    sort(V.begin(), V.end());
    for (int i = 0; i < V.size(); i++)
    {
        cout << V[i] << " ";
    }
    cout << endl;
}
 
void Select(int Idx, int Cnt)
{
    if (Cnt == Select_Num)
    {
        Print_Number();
        return;
    }
 
    for (int i = Idx; i < K; i++)
    {
        if (Visit[i] == true) continue;
        Visit[i] = true;
        V.push_back(MAP[i]);
        Select(i, Cnt+1);
        Visit[i] = false;
        V.pop_back();        
    }
}
 
void Solution()
{
    Select(0, 0);
}
 
void Solve()
{
    while (1)
    {
        Initialize();
        cin >> K;
        if (K == 0) break;
        Input();
        Solution();
        cout << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}