[BOJ] 6603 로또

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

Note

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;
}

2019-01-05 03:42:40에 Tistory에서 작성되었습니다.