백준 6603번 로또

문제 링크 : https://www.acmicpc.net/problem/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이 하나 주어진다. 

 

출력

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

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

 

풀이

조합 문제이다.

이번엔 이전 글에서 설명한 next_permutation 함수를 이용해 조합을 구현해보겠다.

우선 조합을 구현하는데에 이 두가지만 알면 의외로 간단하다.

n개의 수 중 k개를 뽑는다고 하자.

1. vector에 k개의 1을 추가한다.

2. 이후 n-k개의 0 또는 2를 추가한다.

보통 2번 과정에서 0을 추가하는게 일반적이나, 2를 추가해도 별 의미는 없다.

다만, 나중에 뽑을 때 오름차순으로 뽑느냐, 내림차순으로 뽑느냐에 따라 갈리는데 이후에 설명하도록 하겠다.

코드로 표현하자면,

vector ind;
int k = 6; //6개 뽑기

for (int i = 0; i < k; i++) { //k개의 1 추가
ind.push_back(1);
}
for (int i = 0; i < s.size() - k; i++) { //전체크기 - k개의 0 추가
ind.push_back(2);
}
sort(ind.begin(), ind.end());

 

이런식으로 초기 vector를 만들어주고, 

do ~ while문으로 next_permutation을 구현하면서, 배열의 index가 1인것을 print하면 k개의 정렬된 조합이 나온다.

소스코드를 보자.

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int first_check = 1;
    while (1) {
        int t; scanf("%d", &t);
        if (t == 0) break;
        vector<int> s;
        if (first_check == 0) printf("\n");
        first_check = 0;
        for (int i = 0; i < t; i++) {
            int temp; scanf("%d", &temp);
            s.push_back(temp);
        }
        vector<int> ind;
        int k = 6; //6개 뽑기
        
        for (int i = 0; i < k; i++) { //k개의 1 추가
            ind.push_back(1);
        }
        for (int i = 0; i < s.size() - k; i++) { //전체크기 - k개의 0 추가
            ind.push_back(2);
        }
        sort(ind.begin(), ind.end());
        do {
            for (int i = 0; i < ind.size(); i++) {
                if (ind[i] == 1) {
                    printf("%d ", s[i]);
                }
            }
            printf("\n");
        } while (next_permutation(ind.begin(), ind.end()));
        
    }
    return 0;
}

이 문제에선 n-k개의 수를 2로 넣었다.

그 이유는 출력을 사전 순(오름차순)으로 출력하라는 조건때문인데,

next_permutation 함수는 오름차순으로 수열을 구하기때문에

1 1 1 1 1 1 2 2

1 1 1 1 1 2 1 2

1 1 1 1 1 2 2 1 

...

이런식으로 수열을 뽑게되면, 처음부터 차례대로 출력이 가능하다.

반면 0을 넣게 되면,

0 0 1 1 1 1 1 1

0 1 0 1 1 1 1 1

0 1 1 0 1 1 1 1

...

이런식으로 수열을 구하기 때문에 뒤 index부터 출력이 되어 내림차순으로 출력이 된다.

 

이런 사실은 문제에 맞춰 바꿔주면 되겠다.

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~