BOJ 6603 로또

www.acmicpc.net/problem/6603

6603번: 로또

49가지 수 중에서 6개를 뽑아 출력하는 문제다.

백트래킹을 이용한 조합 문제였다.

n과 m을 푼 게 도움이 됐다.

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

void dfs(int cnt, int idx, vector<int>& ar, vector<int>& tmp, vector<bool> vis) {
	if (cnt == 6) {
		for (int i = 0; i < cnt; i++) {
			cout << tmp[i] << ' ';
		}
		cout << '\n';
	}
	else {
		for (int i = idx; i < ar.size(); i++) {
			if (!vis[i]) {
				vis[i] = true;
				tmp[cnt] = ar[i];
				dfs(cnt + 1, i, ar, tmp, vis);
				vis[i] = false;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	while (1) {
		cin >> n;
		if (n == 0) break;
		vector<int> ar(n), tmp(n);
		vector<bool> vis(n, false);
		for (int i = 0; i < n; i++) cin >> ar[i];
		dfs(0, 0, ar, tmp, vis);
		cout << '\n';
	}
	return 0;
}

 

처음에는 next_permutation으로 하려 했으나 조합은 어떻게 구해야 하는지 몰라서 dfs로 직접 구현했다..

 

	for (int i = idx; i < ar.size(); i++) {
		if (!vis[i]) {
			vis[i] = true;
			tmp[cnt] = ar[i];
			dfs(cnt + 1, i, ar, tmp, vis);
			vis[i] = false;
		}
	}

 

순열을 뽑는 경우와 달리 조합을 만들려면 int i = 0 이 아니라 idx를 함수 인자로 넣어줘서 같이 올려줘야 조합이 만들어진다.