6603번: 로또
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로
www.acmicpc.net
문제
독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.
예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.
해설
집합 S의 숫자들 각각에 대한 경우는 2가지로 나뉜다. 로또 6자리에 들어가거나, 안들어가거나. 따라서 재귀를 하되 각 재귀에서 두 갈래로 나뉘도록 재귀를 한다. 이 숫자가 집합에 들어간다면, 집합에 들어갈 수 있는 숫자의 수는 1만큼 줄어든 채로 다음 숫자를 검사한다. 반면 집합에 들어가지 않는다면, 집합에 들어갈 수 있는 숫자의 수는 그대로이며 바로 다음 숫자를 검사한다. 계속 재귀를 돌다가 더이상 집합에 넣을 수 없는 경우, 즉 6가지 수를 모두 뽑은 경우 재귀를 종료하고 돌아간다.
소스코드
#include <iostream>
using namespace std;
void pick(int cnt, int idx,int* arr);
int n;
int list[13] = { 0, };
int main(void)
{
int cnt = 0;
int arr[13] = { 0, };
while (1) {
cin >> n;
if (n == 0)
break;
for (int i = 0; i < n; i++)
cin >> list[i];
pick(cnt,0,arr);
for (int i = 0; i < 13; i++)
list[i] = 0;
cout << endl;
}
}
void pick(int cnt,int idx,int*arr)
{
if (cnt == 6)//더이상 넣지 못하는 경우
{
for (int i = 0; i < n; i++)
{
if (arr[i] == 1)
cout << list[i]<<" ";
}
cout << endl;
return;
}
else
{
if (idx == n)
return;
//넣는 경우
arr[idx] = 1;
pick(cnt + 1, idx + 1,arr);
//넣지 않는 경우
arr[idx] = 0;
pick(cnt, idx + 1,arr);
}
}