[BOJ/C++] 로또(6603번)

1. 개요

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

6603번: 로또

1-1. 설명

독일 로또는 1~49에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 K개의 수를 골라 집합 S를 만든 후 그 수만 가지고 번호를 선택하는 것이다. 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성한다.

1-2. 제한 사항

 - k는 7이상 12이하

 - k개 수는 집합 S에 포함되는 수이며 S는 오름차순

 - 입력 마지막 줄에는 0이 주어짐

---

2. 구현

2-1. 풀이

모든 경우의 수를 세아리기 위해 브루트 포스 재귀 방법을 사용하여 풀이를 진행하였다. 

2-2. 코드 

#include <iostream>
using namespace std;

int nums[13];
int resultNums[6];
int k;

void chooseNum(int len, int index);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while (true) {
        cin >> k;
        if (k == 0) break;

        for (int i = 0; i < k; i++) {
            cin >> nums[i];
        }
        chooseNum(0, 0); // 선택된 로또 길이 및 인덱스
        cout << "\n";
    }
    
    return 0;
}

void chooseNum(int len , int index) {
    if (len == 6) { // 6개 모두 선택시
        for (int num : resultNums) {
            cout << num << ' ';
        }
        cout << "\n";
        return; // 종료
    }

    for (int i = index; i < k; i++) {
        resultNums[len] = nums[i];
        chooseNum(len + 1, i + 1);
    }
}