알고리즘 문제

[백준] 6603번 로또

feelcoding 2020. 1. 29. 00:55
728x90
 

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

www.acmicpc.net

#include <iostream>
using namespace std;

void select(int numbers[], int result[], bool visited[], int n, int num) {
	if (num == 6) {
		for (int i = 0; i < 6; i++) {
			cout << result[i] << " ";
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (num != 0) {
			if (!visited[i] && numbers[i] > result[num - 1]) {
				visited[i] = true;
				result[num] = numbers[i];
				select(numbers, result, visited, n, num + 1);
				visited[i] = false;
			}
		}
		else {
			if (!visited[i]) {
				visited[i] = true;
				result[num] = numbers[i];
				select(numbers, result, visited, n, num + 1);
				visited[i] = false;
			}
		}
	}
}

int main() {
	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;
		int* numbers = new int[n];
		for (int i = 0; i < n; i++) {
			cin >> numbers[i];
		}
		int* result = new int[n];
		bool* visited = new bool[n];
		for (int i = 0; i < n; i++) {
			visited[i] = false;
		}
		select(numbers, result, visited, n, 0);
		cout << endl;
	}
	return 0;
}
728x90