백준 6603번: 로또 (C++)

https://www.acmicpc.net/problem/6603

6603번: 로또

 

n개의 숫자중에 6개를 뽑아서 수열을 만들고, 오름차순 정렬하여 출력해주면 된다.

 

입력으로 들어오는 숫자는 정렬된다는 조건이 없다는 것을 주의해야 한다.

 

 

1. next_permutation 활용 구현

 

#include<iostream>
#include<algorithm>
using namespace std;
int n, a[50], Sel[50];
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) return 0;
		
		for (int i = 0; i < n; i++)
			cin >> a[i];
		sort(a, a + n);
		for (int i = 0; i < n; i++) {
			if (i < 6) Sel[i] = 0;
			else Sel[i] = 1;
		}
		
		do {
			for (int j = 0; j < n; j++) {
				if (!Sel[j]) cout << a[j] << ' ';
			}
			cout << '\n';
		} while (next_permutation(Sel, Sel + n));
		cout << '\n';
	}
	return 0;
}

 

 

2. 백트래킹 활용 구현

 

마찬가지로 사용할 수 있는 수들을 입력 받은 이후에, 수열을 오름차순으로 만들어내기 위해서 정렬을 수행한다.

 

조합이기 때문에 매 재귀마다 0부터 확인하는 것이 아니라 이전 재귀에서 사용했던 숫자의 위치를 파악해서 그 숫자 이후로 사용할 수 있는 숫자를 찾는다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int n, num[50], arr[7];
bool isused[50];
int st;
void func(int k) {
	//여기서 수열의 길이 k
	if (k == 6) {
		for (int i = 0; i < k; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	if (k == 0) st = 0; //0일때 초기화
	for (int i = st; i < n; i++) { //조합으로 만들기 위해 st부터. 0부터 뽑으면 순열(순서가 다르면 다른 수열)
		if (!isused[i]) {
			isused[i] = true;
			arr[k] = num[i];
			st = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			cin >> num[i];
		}
		sort(num, num + n);
		func(0);
		cout << '\n';
	}
}