백준 9997, 폰트 풀이

문제

백준 9997번

풀이

모든 경우의 수를 고려하더라도 시간 복잡도가 $ O(2^N) $ 이므로 시간 내에 해결할 수 있습니다.

그러나, 비트 연산자를 이용해서 탐색하는 경우 시간 복잡도가 $ O(N 2^N) $ 이므로 TLE가 나기 때문에, dfs를 구현하여 풀어야 됩니다.

 

a부터 z를 사용하였는지 체크하는 것은 OR 비트 연산을 사용하여 빠르게 처리할 수 있습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<ll> vec;

int solve(int sz, int vis) {
	if (sz == n) {
		if (vis == (1 << 26) - 1) return 1;
		else return 0;
	}
	return solve(sz + 1, vis | vec[sz]) + solve(sz + 1, vis);
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		ll tmp = 0;
		for (const auto &c : str) tmp |= 1 << (c - 'a');
		vec.emplace_back(tmp);
	}

	cout << solve(0, 0);
}