백준 15663 N과 M (9) (c++) : 피너클

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

15663번: N과 M (9)

구현문제다.

n개중 m개를 선택해야하고, 중복되면 안되고, 사전 순으로 증가하는 순서로 출력해야한다.

수열 중복을 확인하기 위해 map을 이용한다.

int n, m;
int arr[9], id[9];
bool used[9];
map<vector<int>, bool> visited;

선언하는 변수들이다. used는 숫자 중복을 확인한다.

cin >> n >> m;
for (int i = 0; i < n; i++) {
	used[i] = false;
	cin >> arr[i];
}
sort(arr, arr + n);

값을 입력받으며 used를 false로 바꾼뒤 배열을 정렬한다.

vector<int> v;
solve(0, v);

그후 벡터를 하나 선언한뒤 solve를 돌려준다. solve는 (수열크기, 수열)을 전달받는다.

void solve(int num, vector<int> v) {
	if (num == m) {
		if (visited.find(v) != visited.end()) return;
		visited[v] = true;
		for (int i = 0; i < num; i++) cout << v[i] << ' ';
		cout << '\n';
		
		return;
	}

만약 num == m이라면 중복을 확인하고 중복이 아니라면

visited[v] = true 를 한뒤 수열을 출력한다.

	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			used[i] = true;
			v.push_back(arr[i]);
			solve(num + 1, v);
			v.pop_back();
			used[i] = false;
		}
	}
	return;
}

0부터 n까지 반복문을 돌린다.

만약 숫자를 아직 사용하지 않았다면

used[i]를 true로 한뒤

v에 arr[i]를 넣고

solve를 돌린뒤

전부 처음으로 되돌려준다.

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

using namespace std;

int n, m;
int arr[9], id[9];
bool used[9];
map<vector<int>, bool> visited;

void solve(int num, vector<int> v) {
	if (num == m) {
		if (visited.find(v) != visited.end()) return;
		visited[v] = true;
		for (int i = 0; i < num; i++) cout << v[i] << ' ';
		cout << '\n';
		
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			used[i] = true;
			v.push_back(arr[i]);
			solve(num + 1, v);
			v.pop_back();
			used[i] = false;
		}
	}
	return;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		used[i] = false;
		cin >> arr[i];
	}
	sort(arr, arr + n);
	vector<int> v;
	solve(0, v);
}

전체코드다.