[백준] 15654번
💻 C++ 코드
1. 백트래킹 코드
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 9
#define MAX_NUM 10001
using namespace std;
int N, M;
vector<int> input;
int output[MAX];
bool isUsed[MAX_NUM];
void func(int K)
{
if (K == M)
{
for (int i = 0; i < M; i++)
{
printf("%d ", output[i]);
}
printf("\n");
return;
}
for (int i = 0; i < N; i++)
{
if (!isUsed[input[i]])
{
isUsed[input[i]] = true;
output[K] = input[i];
func(K + 1);
isUsed[input[i]] = false;
}
}
}
int main()
{
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
{
int num;
scanf("%d", &num);
input.push_back(num);
}
sort(input.begin(), input.end());
func(0);
return 0;
}
2. next_permutation 코드
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 9
#define MAX_NUM 10001
using namespace std;
int N, M;
vector<int> input;
int output[MAX];
bool isUsed[MAX_NUM];
void func(int K)
{
if (K == M)
{
for (int i = 0; i < M; i++)
{
printf("%d ", output[i]);
}
printf("\n");
return;
}
for (int i = 0; i < N; i++)
{
if (!isUsed[input[i]])
{
isUsed[input[i]] = true;
output[K] = input[i];
func(K + 1);
isUsed[input[i]] = false;
}
}
}
int main()
{
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
{
int num;
scanf("%d", &num);
input.push_back(num);
}
sort(input.begin(), input.end());
func(0);
return 0;
}
✔️ next_permutation의 경우 중복된 수열을 계산해주지 않으므로 우선 M개만큼 뽑은 다음, 새롭게 next_permutation을 돌려 순열을 구해줘야 함
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> input;
vector<int> arr;
vector<vector<int> > output;
int main()
{
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
{
int num;
scanf("%d", &num);
input.push_back(num);
}
sort(input.begin(), input.end());
for (int i = 0; i < M; i++)
{
arr.push_back(0);
}
for (int i = M; i < N; i++)
{
arr.push_back(1);
}
do
{
vector<int> temp;
for (int i = 0; i < N; i++)
{
if (arr[i] == 0)
{
temp.push_back(input[i]);
}
}
do
{
output.push_back(temp);
} while (next_permutation(temp.begin(), temp.end()));
} while (next_permutation(arr.begin(), arr.end()));
sort(output.begin(), output.end());
for (int i = 0; i < output.size(); i++)
{
for (int j = 0; j < output[i].size(); j++)
{
printf("%d ", output[i][j]);
}
printf("\n");
}
return 0;
}
Author And Source
이 문제에 관하여([백준] 15654번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jieun_han/백준-15654번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)