[6603] 로또

Next-Permutation 풀이

1 2 3 5 8 13 21 34이 주어지는 경우, 앞에서부터 1개를 1로 두어 11111100을 만들고 이를 std::prev_permutation을 돌리면서 1의 위치에 있는 값들을 출력한다. 이는 첫번째로 주어지는 숫자 k가 13미만의 작은 수이기 때문에 가능하다.

Next-permutation 코드

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

int main(void) {
	vector<int> v, np;
	int n = 0, t=0;
	while (true) {
		scanf("%d", &n);
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			scanf("%d", &t);
			v.push_back(t);
			if (i < 6) np.push_back(1);
			else np.push_back(0);
		}
		do{
			for (int i = 0; i < np.size(); i++) {
				if (np[i] == 1) {
					printf("%d ", v[i]);
				}
			}
			printf("\n");
		} while (prev_permutation(np.begin(), np.end()));
		printf("\n");
		v = vector<int>();
		np = vector<int>();
	}
	return 0;
}

백트래킹 풀이

void go(int len, vector all, vector sel, int idx) 함수를 만드는데 아래와 같이 진행합니다.

1. len : 몇 개의 값을 선택해야하는가?
2. all : 선택가능한 모든 값을 넣어둔 벡터
3. sel : all에서 현재까지 선택된
4. idx : all에서 idx번째 값을 넣을지 말지 결정

백트래킹의 dfs 개념은 all의 모든 원소를 하나씩 붙혀나간다는 개념으로 변형되었습니다. 그리고 pruning은 sel의 길이가 6이 아니여도 idx를 더이상 늘려갈 수 없을 때 return;를 하는 것으로 적용되었습니다.

백트래킹 코드

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

/*
1. len : 몇 개의 값을 선택해야하는가?
2. all : 선택가능한 모든 값을 넣어둔 벡터
3. sel : all에서 현재까지 선택된
4. idx : all에서 idx번째 값을 넣을지 말지 결정
*/
void go(int len, vector<int> all, vector<int> sel, int idx) {
	if (sel.size() == len) {
		for (int i = 0; i < sel.size(); i++) {
			printf("%d ", sel[i]);
		}
		printf("\n");
		return;
	}
	if (idx >= all.size()) return;
	sel.push_back(all[idx]);
	go(len, all, sel, idx + 1);
	sel.pop_back();
	go(len, all, sel, idx + 1);
}

int main(void) {
	vector<int> all, selected;
	int n = 0, t=0;
	while (true) {
		scanf("%d", &n);
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			scanf("%d", &t);
			all.push_back(t);
		}
		go(6, all, selected, 0);
		printf("\n");
		all = vector<int>();
		selected = vector<int>();
	}
	return 0;
}