문제

https://www.acmicpc.net/problem/13908

---

풀이

특정한 숫자를 반드시 포함해야 한다는 점에서 처음에는 순열과 중복 순열을 이용하려고 했다.

반드시 포함해야 하는 숫자들을 먼저 배치하고, 나머지 자리는 중복 순열로 경우의 수를 구하는!

그런데 이 방법으로는 겹치는 경우의 수가 있기 때문에 그것은 제외시켜줘야 한다.

예를 들어, _ _ _ _ _ 이렇게 5자리 중에 1, 3, 4를 반드시 포함해야 한다고 가정하자.

이를 위해 1, 3, 4를 먼저 순열로 배치하고 -> 5P3 = 5 * 4 * 3

나머지 자리는 0~9 중에 하나로 채우는 것이다. -> 10 * 10

근데 이러면 1340'0 13400' 같이 사실은 동일한 숫자도 다르게 취급하여 중복이 발생하기 때문에, 이러한 중복은 따로 제외시켜줘야 한다.

이 부분에서 까다로움을 느꼈고 이게 맞는 방법인가 확신이 들지 않았다.

결국 답을 보니까 N의 크기가 최대 7밖에 되지 않아서 중복 순열로 전체 경우의 수를 구하고, 그 중에서 M개의 숫자를 모두 포함하지 않는 경우는 정답에서 제외시키면 되는 문제였다.

그래봐야 최대 경우의 수는 10^7 (각 자리수마다 0~9 중에 하나) 이기 때문에, 시간 초과가 발생하지 않을 것이다.

이분 탐색

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 10;
int N, M;
vector<int> contain; // 반드시 포함해야 하는 수
vector<int> v; // 선택된 숫자 저장
int ans = 0;

bool binarySearch(vector<int>& temp, int key){
	int left = 0, right = N - 1;
	
	while(left <= right){
		int mid = (left + right) / 2;
		
		if(temp[mid] == key) return true;
		else if(temp[mid] < key) left = mid + 1;
		else right = mid - 1;
	}

	return false;
}

bool checkPassword(){
	vector<int> temp = v;
	sort(temp.begin(), temp.end());
	
	for(int i = 0; i < contain.size(); i++){
		if(!binarySearch(temp, contain[i])){
			return false;
		}
	}

	return true;
}

// 중복을 허용하므로 selected 배열은 따로 필요 X 
void dfs(int cnt){
	if(cnt == N){
		// 배열 v에 M개의 숫자가 모두 포함되어 있는지 확인 
		if(checkPassword()) {
			ans++;
		}
		return;
	}

	// 순열이므로 인덱스 0부터 시작 
	for(int i = 0; i < MAX; i++){
		v.push_back(i);
		dfs(cnt + 1);
		v.pop_back();
	}
}

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

	cin >> N >> M;

	for(int i = 0; i < M; i++){
		int num; 
		cin >> num;
		contain.push_back(num);
	}

	dfs(0);

	cout << ans;
	
	return 0;
}

실행 시간이 0.6초로 약간 아슬아슬하다.

bool checkPassword(){
	vector<int> temp = v;
	sort(temp.begin(), temp.end()); // O(NlogN)
	
	for(int i = 0; i < contain.size(); i++){ // O(M)
		if(!binarySearch(temp, contain[i])){ // O(logN)
			return false;
		}
	}

	return true;
}

각 경우의 수마다 (최대 10^7) checkPassword 함수에서 이분 탐색을 위해 복사본 배열을 만들고 정렬하는 과정에서 O(NlogN)의 시간복잡도가 걸린다. 그리고 for문에서의 시간복잡도는 O(MlogN)이다.

0 <= M <= N 이므로 checkPassword 함수의 시간복잡도는 O(NlogN)라고 볼 수 있을 것이다.

그냥 선형 탐색은 어떤지 시도해보자.

선형 탐색

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 10;
int N, M;
vector<int> contain; // 반드시 포함해야 하는 수
vector<int> v; // 선택된 숫자 저장
int ans = 0;

bool linearSearch(int key){
	return find(v.begin(), v.end(), key) != v.end();
}

bool checkPassword(){
	for(int i = 0; i < contain.size(); i++){ // O(M)
		if(!linearSearch(contain[i])){ // O(N)
			return false;
		}
	}

	return true;
}

// 중복을 허용하므로 selected 배열은 따로 필요 X 
void dfs(int cnt){
	if(cnt == N){
		// 배열 v에 M개의 숫자가 모두 포함되어 있는지 확인 
		if(checkPassword()) {
			ans++;
		}
		return;
	}

	// 순열이므로 인덱스 0부터 시작 
	for(int i = 0; i < MAX; i++){
		v.push_back(i);
		dfs(cnt + 1);
		v.pop_back();
	}
}

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

	cin >> N >> M;

	for(int i = 0; i < M; i++){
		int num; 
		cin >> num;
		contain.push_back(num);
	}

	dfs(0);

	cout << ans;
	
	return 0;
}

위의 코드에서 checkPassword 함수의 시간복잡도는 O(NM)이다.

실행 시간을 확인해보면, 각 경우의 수마다 배열의 복사본을 만들고 정렬하는 과정이 없어서 오히려 선형 탐색이 더 빠르다는 것을 알 수 있다. 현재 문제처럼 입력의 크기가 작은 경우에는 선형 탐색이 더 유리할 수도 있겠다.