[백준 / C++] N과 M (9)(실버2, 15663)

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

문제

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

• N개의 자연수 중에서 M개를 고른 수열

입력

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

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

예제 입력 1

3 1
4 4 2

예제 출력 1

2
4

예제 입력 2

4 2
9 7 9 1

예제 출력 2

1 7
1 9
7 1
7 9
9 1
9 7
9 9

예제 입력 3

4 4
1 1 1 1

예제 출력 3

1 1 1 1

---

문제 풀이

이번 문제는 결과값이 중복되지 않고, 사전순으로 증가하는 수열들을 출력하는 문제입니다.

 

즉, 완전탐색 방식으로 모든 경우의 수를 체크하며 수열을 만들고, 수열의 크기가 m이 되는 순간 set 컨테이너를 확인해 중복이 아닌 경우 출력하는 방식으로 문제를 해결하게 되었습니다.

코드

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

int n, m;
vector<int> v;
set<vector<int>> s;
bool visited[9];

void Go(int cnt, vector<int> nums)
{
	if (nums.size() == m)
	{
		if (s.find(nums) == s.end())
		{
			for (int i : nums)
			{
				cout << i << " ";
			}
			cout << '\n';

			s.insert(nums);
		}

		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (visited[i] == false)
		{
			visited[i] = true;
			nums.push_back(v[i]);

			Go(i + 1, nums);

			nums.pop_back();
			visited[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int tempNum;
		cin >> tempNum;

		v.push_back(tempNum);
	}

	sort(v.begin(), v.end());

	vector<int>temp;
	Go(0, temp);
	
}