[백준/BOJ] 백준 15663번 : N과 M (9)

www.acmicpc.net/problem/15663

15663번: N과 M (9)

입력받은 숫자를 오름차순으로 정렬한 뒤, 앞에서 부터 숫자를 고르는데, 고른 위치는 중복해서 고르지 않도록 숫자를 골라서 길이가 m인 수열을 만든다. 만들어진 수열은 result에 넣는데, set을 사용해서 같은 수열이 중복되서 추가되지 않도록 했다.

 

코드

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

int n, m;
vector<int> number;
set<vector<int>> result;
set<vector<int>>::iterator it;

void Solve(vector<int>& selected, vector<int>& check)
{
	//m개를 골랐을때
	if (selected.size() == m)
	{
		//result에 넣는다. set이므로 같은 수열이 중복되서 추가되지 않는다
		result.insert(selected);

		return;
	}

	for (int i = 0; i < n; i++)
	{
		//이미 고른 위치일때
		if (check[i] == 1)
			continue;

		//고른 위치의 숫자는 selected에 추가하고 그 위치는 체크한다
		selected.push_back(number[i]);
		check[i] = 1;

		Solve(selected, check);

		//selected에서 제거하고 체크해제
		selected.pop_back();
		check[i] = 0;
	}
}

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

	int input;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		cin >> input;
		number.push_back(input);
	}

	//입력받은 수를 오름차순으로 정렬한다
	sort(number.begin(), number.end());

	vector<int> selected;
	vector<int> check(n, 0);

	Solve(selected, check);

	//구한 수열을 출력
	for (it = result.begin(); it != result.end(); it++)
	{
		for (int i = 0; i < (*it).size(); i++)
			cout << (*it)[i] << " ";

		cout << "\n";
	}

	return 0;
}