[백준] N과 M (9) (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

---

N과 M 문제중에 그래도 가장 까다로운 축에 속한다.

입력으로 들어온 수 자체를 중복해서 사용하면 안 되고, 완성된 배열도 중복되면 안된다.

들어온 수의 중복은 visit 배열을 통해 기록하면 해결할 수 있다.

문제는 완성된 배열의 중복을 확인하는 것인데, 입력으로 들어오는 수의 크기가 작다면 매번 10의 몇 제곱을 곱해서 중복여부를 확인할 수도 있지만, 10000이하의 수가 8개까지 들어오므로 10^32가 되어 다른 방법을 사용하기로 했다.

map을 사용하는 게 해결책이었는데, string 으로 배열을 전환기록해서 string 자체의 중복 여부를 검사한 것이다.

그 외엔 크게 어려운점은 없다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/N%EA%B3%BC%20M%20(9)%20(15663%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;
int N, M;
vector<int> v;
map<string, int> m;
int visit[10];

void dfs(int idx, int cnt, string str) {
	if (cnt == M) {
		if (m[str] == 0) {
			m[str] = 1;
			cout << str << "\n";
		}
		return;
	}

	for (int i = 0; i < N; i++) {
		if (visit[i]) continue;

		string next = str;
		next += to_string(v[i]);
		if(cnt != M-1)
			next += " ";

		visit[i] = true;
		dfs(i, cnt + 1, next);
		visit[i] = false;
	}
}

int main()
{
	cin >> N >> M;
	for (int tmp, i = 0; i < N; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}
	sort(v.begin(), v.end());
	dfs(0, 0, "");
}