[백준] 15663 N과 M (9)

15663번: N과 M (9)

 

boj.kr

풀이

엄청 많은 시리즈가 있는 문제이다. N개의 자연수 중에서 M개를 고르는 것은 백트래킹을 사용해서 어렵지 않게 구현할 수 있다. 하지만 이 문제에는 중복이 발생하기 때문에 중복을 제거해야한다. 아래의 코드에서는 set을 사용해서 중복을 제거했는데, 수열을 string으로 변환해서 set에 넣어주는 방식으로 구현했다. 또한 수열은 사전 순으로 출력해야하므로 맨 처음 입력받은 N개의 자연수를 정렬한 뒤 백트래킹했다.

코드

C++

	#include <iostream>
	#include <algorithm>
	#include <unordered_set>
	using namespace std;
	int n, m;
	int num[10];
	bool chk[10];
	unordered_set<string> chk_set;
	void dfs(int cnt, string s) {
	if (cnt == m) {
	if (chk_set.find(s) == chk_set.end()) {
	cout << s << '\n';
	chk_set.insert(s);
	}
	return;
	}
	for (int i = 0; i < n; i++) {
	if (!chk[i]) {
	string tmp = s + to_string(num[i]);
	tmp += ' ';
	chk[i] = true;
	dfs(cnt + 1, tmp);
	chk[i] = false;
	}
	}
	}
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	cin >> num[i];
	sort(num, num + n);
	dfs(0, "");
	return 0;
	}

view raw 15663.cpp hosted with ❤ by GitHub