[백준] 15650번 - N과 M (2)

www.acmicpc.net

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

문제

💡

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

고른 수열은 오름차순이어야 한다.

시간 제한: 1초

메모리 제한: 128MB

입력

💡

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

💡

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력	예제 출력
3 1	1 2 3
4 2	1 2 1 3 1 4 2 3 2 4 3 4
4 4	1 2 3 4

풀이

N과M (1) 문제에서 순서를 고려하지 않은 수열을 제외하면 똑같은 문제이다. next_permutation 함수를 사용하여 nCm을 구하면 쉽게 풀 수 있다.

생성한 순열에서 조합을 구하기 위해 앞에서부터 m길이까지의 값을 따로 저장한 뒤 정렬한다. 이후 정렬된 순열이 순열배열에 있는지 찾고, 없으면 출력 및 저장한다. 순열배열에 있는지 찾기 위해 정렬을 한번 수행했기 때문에 자연스럽게 사전순으로 출력된다.

코드


#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> vec(n);
	iota(vec.begin(), vec.end(), 1);

	vector<vector<int>> save(8, vector<int>(m));
	vector<int> tmp(m);
	
	do {
		copy(vec.begin(), vec.begin() + m, tmp.begin());
		sort(tmp.begin(), tmp.end());
		if (find(save.begin(), save.end(), tmp) == save.end()) {
			for (auto i : tmp) {
				cout << i << ' ';
			}
			cout << endl;
			save.push_back(tmp);
		}
	} while (next_permutation(vec.begin(), vec.end()));

	return 0;
}