C++ / 백준 / 6603 / 로또

문제

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

6603번: 로또

문제풀이

다음칸을 선택, 선택하지 않는 경우인 두 경우를 나누어 DFS함수를 실행시킨다.

DFS함수의 인자는 현재 위치가 로또의 몇 번째 숫자인지를 idx, 몇 개를 선택했는지가 cnt이다.

6개만 고르면 되므로 cnt가 6일 때 answer에 담은 숫자들을 출력한다.

idx+1이 num보다 작을 때만 DFS함수를 실행하도록 하면 된다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int num;
vector<int>answer(6, 0);
vector<int>lotto;

void DFS(int idx, int cnt) {
	int idx2(0);
	if (cnt == 6) {
		for (idx2 = 0; idx2 < 6; ++idx2)
			cout << answer[idx2] << ' ';
		cout << '\n';
		return;
	}
	if (idx + 1 < num) {
		answer[cnt] = lotto[idx + 1];
		DFS(idx + 1, cnt + 1);
		DFS(idx + 1, cnt);
	}
}

int main() {
	int idx(0);
	while (1) {
		cin >> num;
		if (num == 0) break;
		lotto = vector<int>(num, 0);

		for (idx = 0; idx < num; ++idx)
			cin >> lotto[idx];

		answer[0] = lotto[0];
		DFS(0, 1);
		DFS(0, 0);
		cout << '\n';
	}
}