알고리즘 문제풀이/백준

[백준 6603] 로또

홍시홍 2020. 1. 13. 01:16

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

www.acmicpc.net

요구사항

주어진 수중에서 6개 골라서 출력하기

 

풀이

dfs를 이용하였다.

끝까지 갔을때 고른 숫자가 6개이면 출력

 

#include <iostream>
#include <algorithm>

using namespace std;
int map[14];
int visit[14];
int n;

void dfs(int now, int cnt) {

	if (now == n) {
		if (cnt == 6) {
			for (int i = 0; i < n; i++)
			{
				if (visit[i] == 1) {
					printf("%d ", map[i]);
				}
			}
			printf("\n");
		}
		return;
	}
	visit[now] = 1;
	dfs(now + 1, cnt + 1);
	visit[now] = 0;
	dfs(now + 1, cnt);
}

int main()
{

	while (true) {
		scanf("%d", &n);
		if (n == 0)
			break;
		for (int i = 0; i < n; i++) {
			scanf("%d", &map[i]);
		}
		dfs(0, 0);
		printf("\n");
	}
	return 0;
}