백준 15657 N과 M(8) (c++) : 피너클

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

15657번: N과 M (8)

간단한 구현문제다.

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

값을 입력받고 정렬한다.

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

그후 비어있는 벡터 v를 선언한뒤 solve에 넣어준다.

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

solve함수는 (현재 배열 위치, v에 넣은 숫자 수, 벡터 v)를 전달받는다.

만약 num과 m이 같다면 v값들을 전부 출력하고 바로 함수를 종료한다.

	if (idx == n - 1) {
		for (int i = 0; i < num; i++) cout << v[i] << ' ';
		for (int i = 0; i < m - num; i++)cout << arr[idx] << ' ';
		cout << '\n';
		return;
	}

만약 num==m이 아닌데 idx가 끝까지 왔다면

일단 v값들을 전부 출력한뒤 m - num만큼 arr[idx]값을 출력하고 바로 함수를 종료한다.

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

숫자가 겹쳐도 되니 idx부터 시작해 n까지의 반복문을 만든뒤

v에 arr[i]값을 넣고 solve를 실행한뒤 v에서 arr[i]값을 뺸다.

위의 과정을 반복하면 된다.

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

using namespace std;

int n, m;
int arr[9];

void solve(int idx, int num, vector<int> v) {
	if (num == m) {
		for (int i = 0; i < num; i++) cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	if (idx == n - 1) {
		for (int i = 0; i < num; i++) cout << v[i] << ' ';
		for (int i = 0; i < m - num; i++)cout << arr[idx] << ' ';
		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);
}

전체코드다.