백준 5568 카드 놓기 c++ (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/5568

5568번: 카드 놓기

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

힌트

예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다.

알고리즘 분류

• 자료 구조
• 브루트포스 알고리즘
• 해시를 사용한 집합과 맵
• 재귀

풀이

문제에서 주어진 규칙을 통해 다음과 같은 풀이를 생각할 수 있다.

1. 1, 13, 21, 2 의 카드에서 1, 2 와 2, 1 카드를 뽑았을 때는 12와 21로 다른 정수이다.

  (주어진 리스트의 조합에서 순서가 상관있다.)

2. 1, 13, 21, 2, 3 의 카드에서 2, 1, 13과 21, 1, 3 카드를 뽑았을 때는 2113과 2113로 같은 정수이다.

  (같은 정수에 대한 중복을 없애야 한다.)

 

순서가 상관없는 조합은 재귀(dfs)를 이용한 순열 알고리즘으로 구할 수 있고,

이를 통해 구한 결과는 unordered_set을 이용해 중복을 없앤다.

따라서 중복이 제거되 결과들이 저장되어 있는 unordered_set의 크기가 정답이 된다.

set은 입력 값들을 오름차순 정렬하지만, 여기선 정렬이 필요 없기 때문에 정렬을 하지 않는 unordered_set을 사용했다.

 

코드

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;

int n, k;
//4<=n<=10
//2<=k<=4
unordered_set<string> resultSet;
vector<int> resultVt;
bool visited[10];
void permutation(vector<int> input,int end) {
	if (resultVt.size() == end) {
		string result = "";
		for (int i = 0; i < resultVt.size(); i++) {
			result += to_string(resultVt[i]);
		}
		resultSet.insert(result);
		return;
	}
	for (int i = 0; i < n; i++) {
		if (visited[i]) continue;
		visited[i] = true;
		resultVt.push_back(input[i]);
		permutation(input,end);
		resultVt.pop_back();
		visited[i] = false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	vector<int> input(n);
	for (int i = 0; i < n; i++) {
		cin>>input[i];
	}
	permutation(input,k);
	cout << resultSet.size();
	return 0;
}