[백준/BOJ] 백준 15664번 : N과 M (10)

www.acmicpc.net/problem/15664

15664번: N과 M (10)

입력받은 수를 오름차순으로 정렬한 뒤, 순서대로 숫자를 골라서 길이가 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(int last_selected, vector<int>& selected)
{
	//m개를 골랐을때
	if (selected.size() == m)
	{
		//result에 넣는다. set이므로 같은 수열이 중복되서 추가되지 않는다
		result.insert(selected);

		return;
	}

	for (int i = last_selected + 1; i < n; i++)
	{
		//고른 위치의 숫자는 selected에 추가
		selected.push_back(number[i]);

		Solve(i, selected);

		//selected에서 제거
		selected.pop_back();
	}
}

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;

	Solve(-1, selected);

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

		cout << "\n";
	}

	return 0;
}