[6603] 로또

로또(문제 _ 6603)

독일 로또는 {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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력
각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제

7 1 2 3 4 5 6 7
0

answer :
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

풀이

n과 m 문제를 다 풀었다면 간단히 해결할 수 있는 유형의 문제이다.

n과 m 문제집 링크 https://www.acmicpc.net/workbook/view/2052

백트래킹을 이용해 n(k)의 숫자에서 m(6)개를 뽑아내는 형식의 문제이다.

이때 모든 수열은 사전순으로 출력되어야 하고, 비 내림차순이어야 하는 조건이 있다.

1. 사전순 출력 : vector datas가 오름차순 정렬이 되어있어야 한다 -> 입력이 오름차순으로 들어와서 해결

2. 비 내림차순 : 수열에 값을 넣을 때, 이미 들어와 있는 값보다 큰 값만 넣는다

   if (k == 0 || arr[k - 1] < next)

3. 순서가 다르지만 같은 값을 가진 수열은 같은 수열 : bool isused[] 을 이용해 이미 사용한 값은 수열에 넣지 않는다.

코드

bool isused[50];
int arr[6];
vector<int> datas;

void func(int k) {
    if (k == 6) { // 6개를 뽑았다면 출력한다
        for (int i = 0; i < 6; i++) {
            cout << arr[i] << " ";
        }
        cout << '\n';
        return;
    }

    for (int i = 0; i < datas.size(); i++) {
        int next = datas[i]; // 뽑은 수

        if (!isused[next]) { // 아직 수열에 사용하지 않았다면
            if (k == 0 || arr[k - 1] < next) { // 비 내림차순 조건
                arr[k] = next; // 수열에 넣는다
                isused[next] = true; // 사용했다고 표시한다
                func(k + 1); // 다음 숫자를 뽑으러 간다
                isused[next] = false; // 더이상 사용하지 않는다
            }
        }
    }
}

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

    int k;
    do{
        cin >> k;

        int tmp;
        for (int i = 0; i < k; i++) {
            cin >> tmp;
            datas.push_back(tmp);
        }
        // n개에서 m개 뽑기. 비 내림차순
        // 같은 수열 여러번 출력 불가

        func(0);

        // 사용한 배열들 초기화
        datas.clear();
        memset(arr, 0, sizeof(arr));
        memset(isused, false, sizeof(isused));

        cout << '\n'; // 각 케이스 사이에는 빈 줄을 출력한다.

    } while (k != 0); // k가 0이라면 그만한다.
}

    private static void func(int cur, int idx) {
        if (cur == 6) {
            for (int i = 0; i < 6; i++) {
                sb.append(result[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = idx; i < n; i++) {
            result[cur] = arr[i];
            func(cur + 1, i + 1);
        }
    }