<Baekjoon> #6603 DFS_로또 c++

#6603 로또

1. vector 생성
   먼저 49가지 수 중 k개의 수를 골라 담을 벡터 vector<int> lotto를 만들고 k개중 6개를 뽑아서 넣을 vector<int> ans(N)를 만듦

2. int start, int depth
   dfs 함수를 반복하는데 start, depth 인자를 둔다. start는 vector<int> lotto의 index, depth는 vector<int> ans의 index다.
   즉 depth는 이때까지 뽑힌 로또의 개수이다. 당연히 6개를 넘을 수 없으며 i는 start부터 k까지 반복한다.

e.g. k=7 ,lotto={1,2,3,4,5,6,7} 일 때

3. depth==6일 때는 ans를 출력하고 종료한다.

if (depth == N) {
	for (int i = 0; i < N; i++)
      	  cout<< ans[i] << " ";
	cout << "\n";
		return;
	}

전체 코드

#include <iostream>
#include <vector>

const int N = 6;
using namespace std;

vector<int> ans(N);
vector<int> lotto;
void dfs(int start, int depth, int k) {
	if (depth == N) {
		for (int i = 0; i < N; i++) 
			cout<< ans[i] << " ";
		cout << "\n";
		return;
	}
	for (int i = start; i < k; i++) {
		ans[depth] = lotto[i];
		dfs(i + 1, depth + 1, k);
	}
}

int main() {
	int k;
	while (1) {
		cin >> k;
		if (k == 0) break;
		lotto = vector<int>(k);
		for (int i = 0; i < k; i++)
			cin >> lotto[i];
		dfs(0, 0, k);
		cout << endl;
	}
	return 0;
}