먼저 k 개의 카드를 선택한 후, 해당 카드들의 순열을 구했다.
브루트포스적으로 순열이 만들어내는 결과값들을 set에 넣어 관리했다.(중복을 무시하기 위해서)
위의 내 아이디어는 닭잡는 일에 소잡는 칼을 쓴 것..
k개를 굳이 고르고 k개를 줄세우는 일이 아니더라도
그냥 일반적인 dfs(depth = k)를 통해서도 구할 수 있다.
#include <cstdio>
#include <algorithm>
int N, K;
int pool[10];
bool check[10];
int comb[10 * 9 * 8 * 7];
int comb_size;
void readInput() {
scanf("%d%d", &N, &K);
for (int n = 0; n < N; ++n) {
scanf("%d", &pool[n]);
}
}
void dfs(int _depth, int _sum) {
if (K <= _depth) {
for (int i = 0; i < comb_size; ++i) {
if (comb[i] == _sum)
return;
}
comb[comb_size++] = _sum;
} else {
for (int i = 0; i < N; ++i) {
if (!check[i]) {
check[i] = true;
int n_sum = _sum * (10 <= pool[i] ? 100 : 10) + pool[i];
dfs(_depth + 1, n_sum);
check[i] = false;
}
}
}
}
int main() {
readInput();
dfs(0, 0);
printf("%d", comb_size);
return 0;
}
k 개의 카드의 순열을 구할 때, next_permutation을 사용했는데, next_permutation이 sort가 안돼있을 때 잘 동작하지 않는다는 것을 간과했다.
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<string>
using namespace std;
int arr[10];
//완전탐색 사용
set<string> set_res;
bool comp(int a, int b) {
return a < b;
}
//source를 줄세우기
void genr_perm(vector<int> source) {
sort(source.begin(), source.end(),comp);
do {
string s = "";
for (int i = 0; i < source.size(); i++){
s += to_string(source[i]);
}
set_res.insert(s);
} while (next_permutation(source.begin(), source.end()));
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
vector<bool> jevi;
for (int i = 0; i < n; i++) {
jevi.push_back((i < n - k ? false : true));
}
do {
//k개를 선택하는 과정
vector<int> source;
for (int i = 0; i < n; i++) {
if (jevi[i] == true) {
source.push_back(arr[i]);//1-99라 0이 들어갈 일은 없음
}
}
genr_perm(source);
} while (next_permutation(jevi.begin(), jevi.end()));
cout << set_res.size() << endl;
}