백준 15666 N과 M (12) (c++) : 피너클

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

15666번: N과 M (12)

구현문제다.

n개중 m개를 골라야하고, 같은 수를 여러 번 골라도 되고, 고른 수열은 비내림차순이어야한다.

수열이 중복되는것을 막기위해 map을 이용했다.

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

선언한 변수들이다.

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

값을 입력받고 배열을 정렬한뒤 비어있는 vector하나를 선언한다.

solve(0, 0, v);

그후 solve함수를 돌려준다. solve함수는 (현재 위치, 수열의 크기, 수열)을 전달받는다.

void solve(int idx, 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에 현재 배열이 있다면 바로 함수를 종료하고

아니라면 visited에 v를 true로 넣어준뒤 수열을 출력한다.

	for (int i = idx; i < n; i++) {
		v.push_back(arr[i]);
		solve(i, num + 1, v);
		v.pop_back();
	}
	return;
}

현재 위치부터 끝까지 반복문을 돌린다. 숫자가 겹쳐도 되니 현재 위치부터 돌린다.

v에 arr[i]를 넣고 sovle를 에 v를 넣고 돌린뒤 v에서 arr[i]를 뺀다.

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

using namespace std;

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

void solve(int idx, 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 = idx; i < n; i++) {
		v.push_back(arr[i]);
		solve(i, num + 1, v);
		v.pop_back();
	}
	return;
}

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

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

전체코드다.