BaekJoon 6603 로또

Link : https://www.acmicpc.net/problem/6603

소스 결과 : 1988 KB / 68 ms

출처 : BackJoon / University of Ulm Local Contest 1996 F번

 

설명

DFS를 이용하여 조합을 생성해 출력하는 문제

이와 비슷한 문제도 여럿 존재 하지만 문제 제목이 끌렸다.

 

최대 숫자가 13개 이기에 DFS로 해도 시간이 100ms 이내로 나온다.

 

알고리즘

1. 숫자 k 를 입력받은후 k길이의 vector 생성

2. k개의 숫자를 입력 받은 후 DFS에 사용할 checker 배열 초기화

3. dfs 실행

 3.1 현재 true의 개수가 6개인지 확인, 일치하면 checker에서 true인 값을 출력후 return

 3.2 현재 탐색하는 pos의 checker 값을 true로 바꾼 후 DFS 재귀 실행

 3.3 현재 탐색하는 pos의 checker 값을 false로 바꾼 후 DFS 재귀 실행

4. 다음 k값을 입력 받는다.

 

소스코드

 

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

using namespace std;

void dfs(const vector<int> num, int n, int pos, bool checker[13])
{
	if (n == 6)
	{
		for (int i = 0; i < num.size(); i++)
			if (checker[i])
				cout << num[i] << " ";
		cout << endl;
		return;
	}
	else if (n > 6 || pos == num.size())
		return;

	checker[pos] = true;
	dfs(num, n+1, pos + 1, checker);
	checker[pos] = false;
	dfs(num, n, pos + 1, checker);

}

int main()
{
	int k;

	cin >> k;

	while (k != 0)
	{
		vector<int> num(k);

		for (int i = 0; i < k; i++)
			cin >> num[i];

		bool checker[13];

		fill_n(checker, k, false);

		dfs(num, 0, 0, checker);
		cout << '\n';

		cin >> k;
	}


	return 0;
}