[BOJ / c++] 6603 - 로또

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

6603번: 로또

 

---

해당 문제는 주어진 k개의 숫자를 사용해서 6개의 숫자 조합을 만들어 내는 것이 포인트입니다.

6가지의 숫자 조합을 만들기 위해서 두가지 방식으로 접근을 해봤습니다.

① C++ STL의 prev_permutation() 함수를 이용한 조합 만들기 

• 변수 k의 범위가 6 < k < 13 으로 작은 편이어서 prev_permutation 알고리즘을 사용해도 시간제한 1초를 초과하지 않았습니다.
• 코알라 강의에서 알려주신대로 permutation 알고리즘을 통해서 조합을 구현하기 위해 0과 1로 구성된 인덱스 배열을 선언한 다음 해당 인덱스가 1인 경우 6개의 숫자 조합에 포함되는 방식으로 구현했습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int k;
vector<int> s;

int main() {

	// 입출력 시간 줄이기
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// 각 테스트 케이스 마다 반복
	while (true) {

		// 전역 변수 초기화
		s.clear();

		// 입력 받기
		cin >> k;
		if (k == 0) break;  // 0이 입력되면 최종 종료
		for (int i = 0; i < k; i++) {
			int input;
			cin >> input;
			s.push_back(input);
		}

		// next_permutation 을 통한 조합을 사용해서 6가지 숫자 조합 찾기
		vector<int> comb_idx(6, 1); //  6개의 1 채우기
		for (int i = 0; i < k-6; i++) comb_idx.push_back(0); // 나머지는 0으로 채우기
		do {
			for (int i = 0; i < k; i++) {
				if (comb_idx[i])
					cout << s[i] << " ";
			}
			cout << "\n";
		} while (prev_permutation(comb_idx.begin(), comb_idx.end()));
		cout << "\n";
	}
}

② DFS를 사용한 조합 만들기

• dfs의 파라미터로 현재 선택된 숫자 개수에 해당하는 depth와 함께 다음 숫자 조합을 위한 index를 사용함으로써 숫자 조합을 만들어내는 알고리즘입니다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int k;
vector<int> s;
bool isSelected[13];
vector<int> combinations;

void print_nums() {
	for (auto n : combinations) cout << n << " ";
	cout << "\n";
}

void dfs(int depth, int index) {
	if (depth == 6) {  // 재귀 수행 종료조건 (6개 만큼의 숫자 조합을 만들었을 때 출력)
		print_nums();
		return;
	}
	for (int idx = index; idx < k; idx++) {
		if (isSelected[idx] == true) continue;  // 이미 조합에 포함되어 있으면 다음 숫자 탐색
		combinations.push_back(s[idx]);
		isSelected[idx] == true;
		dfs(depth + 1, idx + 1);
		combinations.pop_back();
		isSelected[idx] == false;
	}
}

int main() {
	
	// 입출력 시간 줄이기
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// 각 테스트 케이스 마다 반복
	while (true) {  

		// 전역 변수 초기화
		memset(isSelected, false, sizeof(isSelected));
		combinations.clear();
		s.clear();

		// 입력 받기
		cin >> k;
		if (k == 0) break;  // 0이 입력되면 최종 종료
		for (int i = 0; i < k; i++) {
			int input;
			cin >> input;
			s.push_back(input);
		}

		// dfs를 통한 숫자 조합 생성 및 출력
		dfs(0, 0);
		cout << "\n";
	}

}