백준 9997번 - 폰트

www.acmicpc.net/problem/9997

9997번: 폰트

• 필요한 배경지식

비트마스킹, 조합론에 대한 지식이 필요합니다.

 

 

• 문제 해결 방법

문제에서 구해야 할 테스트문장은 N개의 단어를 조합하여 만들 수 있으며 소문자'a'부터 'z'까지 26개가 문장에 모두 포함되어 있어야 합니다. 어떻게 N개의 단어를 조합하여 테스트 문장을 만들 수 있을지 생각해 보기전에, 문장안에 a~z까지의 문자가 존재하는지 확인할 방법을 먼저 생각해 봅시다.

 

확인할 개수가 26개밖에 되지 않기 때문에 가장 빠른 방법으로 비트마스킹을 이용하여 O(1)에 모든 문자의 존재를 확인할 수 있습니다. 이렇게 하면 a부터 z까지 모든 알파벳이 포함되어 있을때 마스크는 (1<<26)-1로 표현될 수 있으므로, 특정 단어들을 조합한 문장의 마스크가 (1<<26)-1 이라면 테스트문장의 개수를 늘려주면 됩니다.

 

이제 어떻게 N개의 단어를 조합하여 (1<<26)-1 의 마스크를 가진 테스트문장을 만들지 생각해주어야 합니다.

N의 개수가 25개 이므로 완전탐색을 이용해도 시간안에 들어올것 같습니다.

계산을 해보면, nC0 + nC1 + nC2 + nC3 + .... + nCn = 2^N 이므로 2^25 = 33,554,432 으로 충분히 1초안에 들어올 수 있습니다. 그렇다면 조합을 구현하기 위해 가장 만만한 재귀를 이용하면 문제를 해결할 수 있습니다.

 

 

 

• C++ 전체 코드

// 비트마스킹을 이용
#include<bits/stdc++.h>
using namespace std;

int N;
int mask[25]{}; // 비트마스크
int ans = 0;

// 완전탐색 2^N
void solve(int n, int curMask){
    if(curMask==(1<<26)-1) ans++;

    for(int i=n+1; i<N; i++){
        int nextMask = (curMask | mask[i]);
        solve(i, nextMask);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin>>N;
    for(int i=0; i<N; i++){
        cin>>s;
        // n번째 단어의 마스크 mask[i]
        for(int j=0; j<s.size(); j++){
            int t = s[j]-'a';
            mask[i] |= (1<<t);
        }        
    }

    solve(-1,0);
    cout<<ans;
}