[백준15664] N과 M (C++)

📌 문제

BOJ 바로가기

N개의 숫자 중 M개의 숫자를 뽑아 비내림차순의 수열을 만들어야 한다. 단, 수열이 중복되면 안 된다.

🗡 풀이

검색해보니 비트마스크 풀이는 잘 없길래 내가 써보기로 했다.

📍 비트마스크를 이용해 공집합이 아닌 모든 부분집합을 탐색한다.

📍 M개의 숫자를 골랐을 경우에 고른 숫자들을 벡터에 넣어서 수열을 만든다.

📍 set에 벡터를 담는다. 중복되는 수열이 있다면 set에 담기는 과정에서 알아서 제외된다.

🚩 소스코드

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

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m, num[8];
	set<vector<int>> ans;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + n);
	// 비트마스크. 모든 부분집합 탐색
	for (int s = 1; s < (1 << n); s++) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			if (s & (1 << i))
				cnt++;
		}
		if (cnt == m) {
			vector<int> v;
			for (int i = 0; i < n; i++) {
				if (s & (1 << i))
					v.push_back(num[i]);
			}
			ans.insert(v);
		}
	}
	for (auto x : ans) {
		for (int y = 0; y < m; y++)
			cout << x[y] << ' ';
		cout << '\n';
	}
	return 0;
}