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

 

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이 하나 주어진다. 

출력

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

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

예제 입력 1 복사

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력 1 복사

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

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

---

[문제 풀이]

이 문제는 1-49, 49개의 숫자 중 입력으로 들어오는 숫자들에서 6개의 숫자를 선택하여 만든 순열을 모두 찾아서 출력해주면 된다. 중복은 안된다.

원래 같았다면, 모든 경우를 백트랙킹을 이용하여 구했을것 같지만,

next_permutation(), prev_permutation() 함수를 사용하면 편하게 문제를 풀 수 있을 것 같다는 생각을 했다.

 

내가 푼 방법은 아래와 같다.

1. 입력으로 들어오는 숫자들의 개수를 저장한다.

 -> 0이면 종료

2. 입력되는 숫자들을 저장할 벡터와 순열을 계산하기 위한 벡터를 준비한다.

2.1 순열을 계산하기 위한 벡터는 앞에서부터 6개에 1로 채워둔다. (앞에서 부터 6개의 숫자를 선택)

3. 미리 앞부분에 1을 6개 채워둔 벡터와 prev_permutation() 함수를 이용하여 순열을 찾아준다.

4. 입력되는 숫자들의 개수만큼 반복문을 돌며 순열을 찾기 위한 벡터의 값이 1인 경우 해당 인덱스의 값을 출력해준다.

예제 2번을 예로 들면,

 1 2 3 5 8 13 (21) (34)      ->         (1) (2) 3 5 8 13 21 34     

    (1 1 1 1 1 1 0 0)            ->            ( 0 0 1 1 1 1 1 1 ) 

5. 입력된 숫자들의 순열을 모두 찾아 출력이 끝났을 경우, 줄바꿈을 꼭 해주고 벡터들을 초기화 해주어야 한다.

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    while(1)
    {
        int t = 0;
        cin >> t;
        if(t==0) break;
        vector<int> nums(t,0);
        vector<int> isCheck(t,0);
        for(int i =0; i < t; i++) { cin >> nums[i];}
        for(int i =0; i < 6; i++) { isCheck[i] = 1;}
        
        do
        {
            for(int i =0; i < t ;i++)
            {
                if(isCheck[i]) cout << nums[i] << " ";
            }
            cout << "\n";
        }
        while(prev_permutation(isCheck.begin(), isCheck.end()));
        cout << "\n";
        nums.clear();
        isCheck.clear();
    }
}