[백준]Baekjoon6603[순열]

문제링크 : https://www.acmicpc.net/problem/6603

풀이

주어진 k개의 번호중 6개를 골라 만들 수 있는 경우를 모두 구하는 문제이다.

6개를 고르기 위해 순열의 특성을 이용했는데 

예를들어 숫자가 7개가 있다고 가정하고 0을 1개 1을 6개를 배열에 넣고

모든순열을 구하면 다음과같이 나온다.

이 부분에서 아마 이 문제를 어떻게 풀어야할지 대충 감이 왔으리라 생각된다.

이렇게 k-6개에 대해 0을 넣고 k개의 1을 넣은 후 순열을 돌렸을 때 

1이 있는 곳과 대응되는 자리의 수를 출력하면 모든 경우를 구할 수 있는것이다.

소스코드는 다음과 같다.

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

using namespace std;

int main()
{
	while (1) {
		int arr[13];
		vector<int> testcase;

		int k;
		scanf("%d", &k);
		if (k == 0) break;

		int zero = k - 6;
		for (int i = 0; i < zero; i++) arr[i] = 0;
		for (int i = zero; i < k; i++) arr[i] = 1;
		//arr에 6개의 1과 k-6에 대해서 1을 넣어주는 과정

		int num;
		for (int i = 0; i < k; i++) {
			scanf("%d", &num);
			testcase.push_back(num);
		}

		vector<vector<int>> answer;
		do {
			vector<int> current;
			for (int i = 0; i < k; i++) {
				if (arr[i] == 1) current.push_back(testcase[i]);
			}
			answer.push_back(current);
		} while (next_permutation(arr,arr+k));
		for (int i = answer.size()-1; i >= 0; i--) {
			for (auto x : answer[i]) printf("%d ", x);
			printf("\n");
		}
		printf("\n");
	}
}

위에서 설명해놓은 과정을 그대로 구현해놓은 코드이다.

여기서 왜 이중 vector를 사용했는지에 대한 추가 설명을 하자면

만약 따로 저장과정없이 1에 대응하는 수를 바로 출력하면 다음과같이 나온다.

사전순의 역순으로 나오는 것이다.

고로 나온 수를 먼저 vector함수에 저장한다음 역순으로 출력해주어

사전순으로 출력할 수 있게끔 해주는 것이다.