1410 : 패턴의 개수

풀이

bitmask dp를 해보자!

근데 이거 풀이를 어떻게 써야하지

dp[len][bit] = 패턴의 길이를 len까지만 놓고 볼 때, 마스킹 된 패턴에만 일치하는 길이 len짜리 문자열의 수

코드

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

const int mod = 1000003;

int n, k;
int dp[50][1 << 15];
string str[15];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> str[i];

	int len = str[0].size();

	for (int i = 0; i < len; ++i) {
		for (char c = 'a'; c <= 'z'; c++) {
			int v = 0;
			for (int j = 0; j < n; j++) {
				if (str[j][i] == c || str[j][i] == '?') {
					v |= (1 << j);
				}
			}
			if (!i) {
				dp[i][v]++;
			}
			else {
				for (int j = 0; j < (1 << n); j++) {
					dp[i][j&v] = (dp[i][j&v] + dp[i - 1][j]) % mod;
				}
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < (1 << n); i++) {
		int bit = 0;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				bit++;
			}
		}
		if (bit == k) {
			ans = (ans + dp[len - 1][i]) % mod;
		}
	}

    cout << ans;

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-02-15 21:32

Read more posts by this author