vector
생성
먼저 49가지 수 중 k개의 수를 골라 담을 벡터vector<int> lotto
를 만들고 k개중 6개를 뽑아서 넣을vector<int> ans(N)
를 만듦
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}
일 때
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; }