# 생각
주어진 수 중에서 한번이라도 사용된 수는 더이상 사용되지 않으므로
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)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열
www.acmicpc.net
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 15664_N과 M(10) with cpp (0) | 2022.02.07 |
---|---|
[BOJ] 15663_N과 M (9) with cpp (0) | 2022.02.06 |
[BOJ] 15651_N과 M (3) with cpp (0) | 2022.02.05 |
[BOJ] 1182_부분수열의 합 with cpp (0) | 2022.02.03 |
[BOJ] 9663_N-Queen with cpp (0) | 2022.02.01 |