[BOJ] 15654_N과 M (5) with cpp

# 생각

주어진 수 중에서 한번이라도 사용된 수는 더이상 사용되지 않으므로

bUsed를 이용하여 걸러준다

또한 이전 문제들과는 달리 수의 입력이 주어지므로

num배열을 추가로 선언하여 작성해주면 해결이 가능하다

 

 

# 전체 코드

// 1s, 512MB
// 1 <= M <= N <= 8
#include <bits/stdc++.h>
using namespace std;

int arr[10];
bool bUsed[10];
int num[10];

void funcRecursive(int k, int n, int m)	// 현재 k개까지 수를 선택했다
{
	if (k == m)	// m개를 모두 택했다면
	{
		for (int i = 0; i < m; i++)
		{
			cout << num[arr[i]] << ' ';	// arr에 기록해둔 인덱스에 대응되는 수 출력
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++)	// 0 부터 n-1까지의 인덱스에 대해
	{
		if (bUsed[i] == false)	// 아직 i가 사용되지 않았으면
		{
			arr[k] = i;	// k번째 인덱스를 i로 정함
			bUsed[i] = true;	// i 사용
			funcRecursive(k + 1, n, m);	// 다음 인덱스 정하러 한 단계 더 진행
			bUsed[i] = false;	// k번째 인덱스를 i로 정한 모든 경우에 대해 다 확인했으니 i 미사용으로 전환
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

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

 

 

# next_permutation을 이용한 코드

#include<bits/stdc++.h>
using namespace std;

int n, m, arr[8];

void dfs2()
{
	do
	{
		reverse(arr + m, arr + n);
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
	} while (next_permutation(arr, arr+n));
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

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

 

---

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

15654번: N과 M (5)