백준 15633 N과 M(9) 풀이

사용언어

Visual studio 2019 C++

유형

c++ stl <map> 사용

[15663 풀이]

#include <iostream> 
#include <vector>
#include <map>
#include <algorithm> 

#define MAX 8
#define endl "\n"
using namespace std;

int n, m;
vector<int> v;
int visited[MAX];
map<int, int> numberCnt;

void NandM(int idx, int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++)
			cout << v[visited[i]] << " "; // visited[i] 는 배열의 idx 
		cout << endl;
		return;
	}
	if (idx == n)
		return;

	for (int i = 0; i < v.size(); i++) {
		if (numberCnt[v[i]]) {
			numberCnt[v[i]]--; // 숫자의 cnt-1

			visited[idx] = i; // idx에 i를 넣는다
			NandM(idx + 1, cnt + 1); // 둘

			numberCnt[v[i]]++;
		}
	}
}

void init() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main() {
	init();
	cin >> n >> m;

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

		if (!numberCnt.count(a)) { // 그 숫자가 아직 numcount vector에 없다면
			numberCnt[a] = 1; // 1을 넣고
			v.push_back(a); // 추가
		}
		else
			numberCnt[a]++; // 숫자가 존재하므로 +1
	}
	sort(v.begin(), v.end());

	NandM(0, 0);
}