[Brute Force] BOJ 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이 하나 주어진다. 

 

출력

---

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

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

 

풀이

---

 

 

지금 부터 완전탐색을 통해서 문제를 해결할것이다. 

우리는 number라는 재귀함수를 만들어서 모든 경우의 수를 확인해볼 것이다.

 

 

number의 인수를 먼저 보자.

1. 배열은 모든 로또 번호가 입력된 배열이다.

2. 하나씩 확인해볼 배열의 index 를 의미한다.

3. 선택한 번호의 개수를 의미한다.

 

 

 

첫번째 줄에 if 문은 로또 번호를 6개 선택했을 경우

선택한 번호를 모두 출력하는 문장이다.

 

 

두번째 if 문에서 index가 size와 같아지는 경우는

모든 번호를 돌았음에도 불구하고 6개를 선택하지 못한 경우를 의미한다.

이런경우 함수를 종료한다.

 

 

세번째로 벡터로 구현된 배열에 입력하는 부분이다.

선택한 경우 와 선택하지 않은 경우로 나뉜다.

 

 

여기서 해당 번호를 선택했다면 배열에 해당번호를 넣고

index 와 cnt 를 모두 증가시킨다.

 

 

선택하지 않은 경우는 방금 lotto에 넣었던 번호를 다시 pop 한 후

index 만 1 증가시켜서 재귀호출한다.

 

 

코드

---

#include <iostream>
#include <vector>

using namespace std;

vector <int> lotto; //출력할 번호 저장

void number(vector<int> &a, int index, int cnt) {
	if (cnt == 6) { // 6개를 골랐으면 번호 출력
		for (int a : lotto) {
			cout << a << ' ';
		}
		cout << '\n';
		return;
	}
	int s = a.size();
	if (index == s) return;
	// 입력된 번호를 전부 돌았는데도 번호를 선택하지 못한경우
	// 그 순간 해당 재귀함수는 종료된다.

	lotto.push_back(a[index]); //번호를 선택한 경우
	number(a, index + 1, cnt + 1); 
	//해당 번호를 선택했으니 index,cnt 모두 1씩 증가
	lotto.pop_back(); //선택을 안하는 경우 방금 push한 값을 제거
	number(a, index + 1, cnt);
	//선택을 안했으니 index 만 1증가

}

int main()
{
	while (1) {
		int n;
		cin >> n;
		if (n == 0) break;
		//번호가 없는 경우 종료
		vector<int> a(n); // 입력받는 번호를 저장

		for (int i = 0; i < n; i++) { //번호입력
			cin >> a[i];
		}

		number(a, 0, 0);
		cout << '\n';
	}

	return 0;
}