[백준] 5568 카드 놓기

문제 요약

• 카드가 n 개 있다.(4<=n<=10)
• 이 중에서 k 개의 카드를 꺼내서 순서를 내맘대로 설정해서 숫자를 만들 수 있다.
• 이렇게 만들 수 있는 숫자의 가짓수는 몇개일까요??

아이디어

먼저 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;
}