<Baekjoon> #6603 DFS_로또 c++

#6603 로또

  1. vector 생성
    먼저 49가지 수 중 k개의 수를 골라 담을 벡터 vector<int> lotto를 만들고 k개중 6개를 뽑아서 넣을 vector<int> ans(N)를 만듦
  1. int start, int depth
    dfs 함수를 반복하는데 start, depth 인자를 둔다. startvector<int> lotto의 index, depthvector<int> ans의 index다.
    depth는 이때까지 뽑힌 로또의 개수이다. 당연히 6개를 넘을 수 없으며 istart부터 k까지 반복한다.

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

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

좋은 웹페이지 즐겨찾기