백준 6603_로또(C++)

 

www.acmicpc.net/problem/6603

6603번: 로또

[문제 풀이]

조합을 이용하여 문제를 풀었습니다.

이 문제는 숫자 K와 K개의 숫자 집합이 주어졌을 때, 집합의 원소로 이루어져 있는 6개의 숫자를 뽑는 문제였습니다. N개의 숫자에서 C개의 숫자를 뽑는 것이기에 조합을 이용하여 문제를 해결했습니다.

 

코드 설명

• N개의 숫자를 입력받은 후 N - 6 만큼 반복문을 돌면서 6개 번호 중 첫 번째 번호를 정해 줍니다.
• combination 함수를 이용하여 나머지 다섯 개의 번호를 위와 같은 방법으로 재귀를 통해 찾아줍니다.
• 6개의 숫자가 선택되었다면 숫자를 출력해 줍니다. 

[코드]

#include<iostream>
#include<vector>

using namespace std;

int N;

int six_num[6] = { 0, };

vector<int> lotto_num;

void combination(int, int);

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (1) {

		cin >> N;

		if (N == 0)
			return 0;
		else {

			for (int i = 0; i < N; i++) {
				int temp; cin >> temp;
				lotto_num.push_back(temp);

			}

			for (int i = 0; i <= N - 6; i++) {
				six_num[0] = lotto_num[i];
				combination(i, 1);
				six_num[0] = 0;
			}

			lotto_num.clear();
		}
		cout << endl;
	}

	return 0;

}

void combination(int idx, int cnt) {

	if (cnt == 6) {
		for (auto item : six_num)
			cout << item << " ";
		cout << endl;
		return;
	}

	for (int i = idx + 1; i < N; i++) {
		six_num[cnt] = lotto_num[i];
		combination(i, cnt + 1);
		six_num[cnt] = 0;
	}

}