취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 9997번 문제인 폰트이다.
문제는 아래 링크를 확인하자.

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

주어지는 각 문자열이 포함하는 문자들을 정리한 뒤, 모든 문자가 포함된 폰트 모음의 개수를 세어 문제를 해결하자.

각 문자열을 i번째 알파벳을 i번째 비트로 대응시켜 정수 하나로 표현하면 이 과정을 매우 빠르게 진행할 수 있다.

또한, 문자열의 집합을 둘로 나누어 각 집합의 선택 경우의 수를 모두 나열하고 이것들을 각각 대응시켜보는 MITM 접근도 유효하다.

아래는 제출한 소스코드이다.

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

int N, K;
int ans, A[25];
string s;
vector<int> vec1, vec2;

void dfs1(int cur, int val) {
	if (cur == N / 2 + 1) {
		vec1.emplace_back(val);
		return;
	}
	dfs1(cur + 1, val);
	dfs1(cur + 1, val | A[cur]);
}
void dfs2(int cur, int val) {
	if (cur == N) {
		vec2.emplace_back(val);
		return;
	}
	dfs2(cur + 1, val);
	dfs2(cur + 1, val | A[cur]);
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s;
		for (auto &l:s) A[i] |= (1 << (l - 'a'));
	}

	dfs1(0, 0);
	dfs2(N / 2 + 1, 0);
	K = (1 << 26) - 1;
	for (auto &x:vec1) {
		for (auto &y:vec2) {
			if ((x | y) == K) ans++;
		}
	}
	cout << ans;
}