[C++] 백준 6603번: 로또

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

6603번: 로또

1. 문제 풀이

 집합 S에 존재하는 로또 번호 중 6개의 번호를 선택하여 나열하는 모든 순열의 수를 완전 탐색을 이용하여 구하였다. 집합 S에서 6개의 원소를 선택하여 나열하기 위해, 집합 S의 개수만큼 0으로 채워진 벡터 V를 만들고, 0부터 5번째 인덱스까지 1을 채운다. 그 후, algorithm 헤더 파일의 prev_permutation 함수를 사용하여 벡터 V의 모든 순열의 수를 탐색한다. 벡터 V를 탐색할 때 원소가 1인 경우, 그 인덱스에 해당하는 집합 S의 원소를 출력한다. 반복문을 돌면서 출력되는 예는 다음과 같다.

- 1번째 탐색
S = {1, 2, 3, 5, 8, 13, 21, 34}
V = {1, 1, 1, 1, 1, 1, 0, 0}
출력: 1 2 3 5 8 13

- 2번째 탐색
S = {1, 2, 3, 5, 8, 13, 21, 34}
V = {1, 1, 1, 1, 1, 0, 1, 0}
출력: 1 2 3 5 8 21

- 마지막 탐색
S = {1, 2, 3, 5, 8, 13, 21, 34}
V = {0, 0, 1, 1, 1, 1, 1, 1}
출력: 3 5 8 13 21 34

2. C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;

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