Baekjoon 5568 카드 놓기

Link https://www.acmicpc.net/problem/5568

소스결과 2364 KB / 64 ms

출처 Baekjoon

언어 C++ 17

분류 브루트포스, 이분탐색

 

설명

n 개의 카드중 k를 사용하여 만들 수 있는 정수의 모든 경우를 출력해주자.

 

딱봐도 모든 경우에 대해서 전수조사후 Map이나 Set에 모두 넣으면 되는 문제다.

알면서도 다르게 귀찮게 풀어보는게 이번 문제의 재미인거 같다.

새로운 값을 발견 할 때마다 이분탐색을 통해 해당 값이 존재하는지 확인 후, 존재하지 않으면 vector에 넣은 후 정렬을 반복하는 방식을 선택했다.

 

알고리즘

1. n개의 카드를 입력받는다.

2. n개중 k개를 선택하는 순열을 반복한다.

3. 기존 값 * 이번에 선택하는 카드의 자리수 + 이번 카드를 다음 값으로 넘겨준다.

4. 결과값을 저장하는 배열을 이분탐색하여 값이 존재하는지 탐색한다.

5. 존재하지 않는 경우 값을 push한다.

6. 결과 배열의 크기를 출력한다.

 

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<long long> save;
int n, k;

void permutation(const vector<int>& cards, vector<bool>& checker, int pos, int cnt, long long sum) {

	if (pos < n && cnt < k) {
		for (int i = 0; i < n; i++) {
			if (checker[i]) continue;
			int _log = log10(cards[i]) + 1;
			int digit = pow(10, _log);
			checker[i] = true;
			permutation(cards, checker, pos + 1, cnt + 1, sum * digit + cards[i]);
			checker[i] = false;
		}
	}
	else
	{
		if (cnt == k) {
			//cout << sum << '\n';
			int lower = lower_bound(save.begin(), save.end(), sum) - save.begin();
			int upper = upper_bound(save.begin(), save.end(), sum) - save.begin();

			if (upper - lower < 1) {
				save.push_back(sum);
				sort(save.begin(), save.end());
			}
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;

	vector<int> cards(n);
	vector<bool> checker(n, false);

	for (int i = 0; i < n; i++)
		cin >> cards[i];

	permutation(cards, checker, 0, 0, 0);

	cout << save.size();

	return 0;
}