백준 6603. 로또

알고리즘 기초 문제 중 브루트포스-순열 문제(520)

로또

1. 간단 설명

독일 로또는 국내와는 다르게 1~49의 수 중에서 6개를 고른다고 한다

49개의 수 중 k개를 골라, 이 집합으로 6개의 숫자를 고르는 경우를 모두 출력하는 문제

즉, kC6을 모두 출력하면 된다

2. 예시

k = 8, S = {1,2,3,5,8,13,21,34} 인 경우,

([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

8! / (6! * 2!) = 28가지를 모두 출력하면 된다

3. 알고리즘

완전 탐색을 이용해 조합을 생성하여 출력한다

먼저 직접 구현하는 방법으로 풀어보고, STL next_permutation을 이용한 방법으로도 풀어볼 예정

1. k를 입력받는다. k가 0이라면 종료한다
2. 집합 s의 수들을 입력받는다
3. 이 수들 중 6개를 뽑아서 조합을 생성하여 출력한다
4. 모든 조합의 경우의 수를 모두 출력한다
5. 2-4를 반복한다

필요 변수들

• int k (6 < k < 13)
• 집합 s를 저장할 배열 vector<int> v. 각 원소는 1~49의 숫자 중 하나 이후는 어떤 구현 방식을 사용하느냐에 따라 추가로 필요 변수들이 달라짐
• 직접 구현한다면
  • 결과 출력용 vector<int> result
  • 조합 구현을 위한 해당 숫자 사용 여부 체크용 visited[50]
  • 조합 함수(int level, int start)
• next_permutation을 이용해 조합을 구현한다면
  • index용 벡터 vector<int> idx
    • 왜 index용 벡터가 필요한지 알고싶다면 해당 링크 참조

4. 소스코드

직접 구현한 조합 버전

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

int k;
vector<int> result;
vector<int> v;
int visited[50];

// 재귀적으로 조합 구현. 현재 레벨과 시작 index를 매개변수로 받음
void combination(int level, int start) {
	if (level == 6) {
		for (int e : result) {
			cout << e << ' ';
		} cout << '\n';
		return;
	}

	for (int i = start; i < k; i++) {
		if (visited[i] == 1) continue;

		visited[i] = 1;
		result.push_back(v[i]);

		combination(level + 1, i+1);

		visited[i] = 0;
		result.pop_back();
	}

}

int main(){
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> k;
	while (k != 0) {
		// 테스트케이스별 초기화
		v.resize(k);
		result.clear();
		memset(visited, 0, sizeof(visited));

		// 입력받기
		for (int i = 0; i < k; i++) {
			cin >> v[i];
		}

		// 조합 생성
		combination(0, 0);
		cout << '\n';

		cin >> k;
	}
	
	return 0;
}

• next_permutation을 이용한 조합

#include <bits/stdc++.h>

using namespace std;

int main(){
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	while (1) {
		int k;	cin >> k;
		if (k == 0) break;

		// 1. 입력받기
		vector<int> v(k);
		for (int i = 0; i < k; i++)
			cin >> v[i];

		vector<int> idx; // 조합을 위한 index 벡터. next_permutation으로 조합 생성용
		for (int i = 0; i < 6; i++) // 0일떄 뽑는다
			idx.push_back(0);

		for (int i = 0; i < k - 6; i++) // 1일때 거른다
			idx.push_back(1);

		// 조합 생성
		do {
			for (int i = 0; i<v.size(); i++) {
				if (idx[i] == 0) { 
					cout << v[i] << ' ';
				}
			} cout << '\n';

		} while (next_permutation(idx.begin(),idx.end()));
		cout << '\n';
	}
	
	return 0;
}