BOJ 1410 패턴의 개수

* BOJ 1410 패턴의 개수

[분류 : 다이나믹 프로그래밍, 비트셋]

  1. [같은 길이의 패턴] 길이가 다른 패턴은 절대 같은 단어를 포함할 수 없다. 같은 길이끼리만 모아서 생각해보자.

  2. [비트 셋] 집합의 크기가 아무리 커봐야 15이므로 비트 셋을 쓰기에 충분히 작다. 또 2^15의 배열의 크기로도 충분히 작음을 알 수 있다.

  3. [다이나믹 구성] 1.에 있는 조건을 가져와서 같은 길이를 가지는 패턴들만 생각해보자. 

  dp[p][s]=p위치에 있는 문자를 결정해야하고, 현재 겹치는 패턴의 집합이 s일 때, 일치하는 패턴의 수가 정확히 K인 경우의 수

  p이전에 선택한 문자들이 모두 일치하는, 또는 문자 ?로 대체할 수 있었던 패턴들이 s 비트 셋에 담겨있다. 현 위치 p에서 문자 a-z를 선택하며 p위치에 선택한 문자와 적합하지 않은 패턴들은 모두 비트 셋에서 제거한다. 그 이후 같은 방식으로 부분 문제를 풀어나가면 된다.

(참고) 비트 셋에서 1로 설정된 값(여기서는 적합한 패턴의 인덱스)의 개수를 빌트인 함수 __builtin_popcount함수를 쓰면 바로 계산할 수 있다. 하지만 이 함수는 gcc 환경에서만 쓸 수 있으므로 컴파일 환경을 보고 사용하도록 하자.

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAX_N = 15, MAX_L = 50, MOD = 1e6 + 3;
int N, K, dp[MAX_L][1 << 15], b[MAX_N][MAX_L], L[MAX_N], curL;
vector<int> indices;
int rec(int p, int s) {
	if (p == curL) return __builtin_popcount(s) == K;
	int& ret = dp[p][s];
	if (ret != -1) return ret;
	ret = 0;
	int i, t;
	for (i = 0; i < 26; i++) {
		t = s;
		for (int& j : indices) if (((1 << j) & s) && !(b[j][p] == -1 || b[j][p] == i))
			t ^= (1 << j);
		ret = (ret + rec(p + 1, t)) % MOD;
	}
	return ret;
}
int main() {
	char d[MAX_L + 1];
	int i, j, used[MAX_N] = {}, ans = 0;
	memset(dp, -1, sizeof dp);
	scanf("%d%d\n", &N, &K);
	for (i = 0; i < N; i++) {
		scanf("%s", d);
		for (j = 0; d[j]; j++)
			b[i][j] = d[j] == '?' ? -1 : d[j] - 'a';
		L[i] = j;
	}
	for (i = 0; i < N; i++) if (!used[i]) {
		indices.clear();
		used[i] = 1;
		indices.push_back(i);
		for (j = i + 1; j < N; j++) if (L[i] == L[j]) {
			used[j] = 1;
			indices.push_back(j);
		}
        curL = L[i];
		ans = (ans + rec(0, (1 << indices.size()) - 1)) % MOD;
	}
	printf("%d", ans);
	return 0;
}