BOJ-15654 N과 M (5)

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

문제 소개

자연수 N과 자연수 M, 그리고 N개의 자연수가 주어졌을 때 N개의 자연수 중 M`개를 고른 수열을 모두 구하는 프로그램을 작성한다.

문제 풀이

algorithm 라이브러리의 next_permutation()함수를 이용하여 vector<int>에 입력받은 N개의 자연수에 대하여 순열을 구하였다.

next_permutation()은 대상 컨테이너의 원소가 정렬된 형태의 다음 순서에 해당하는 순열로 컨테이너를 변화시키므로 최초에는 sort()를 통한 정렬이 필요하다.

next_permutation()은 컨테이너에서 사용할 원소의 개수를 지정하지는 못한다. 그러므로 특정 개수(M)까지만 출력하는 방식으로 문제의 요구를 충족시켰다.

하지만 이 경우 앞의 M개 원소의 순서가 같고 나머지 N - M개 원소의 순서가 다른 경우에는 똑같은 순열로 중복 출력하게된다는 문제가 있으므로, 중복되는 경우의 수인 (N - M)!를 활용하여 중복되지 않게 한 번씩만 출력하도록 하였다.

코드

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

int factorial(int x) {
	int result = 1;
	for (int i = 1; i <= x; i++) {
		result *= i;
	}
	return result;
}

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	vector<int> arr;

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		arr.push_back(t);
	}
	// (N - M)!
	int d = factorial(n - m);

	// 정렬
	sort(arr.begin(), arr.end());

	int acc = 0;
	do {
		acc += 1;
		if (acc == d) {
			for (int i = 0; i < m; i++) {
				cout << arr[i] << ' ';
			}
			cout << "\n";
			acc = 0;
		}
	} while (next_permutation(arr.begin(), arr.end()));

	return 0;
}