[BOJ/백준][Gold2] 9997 : 폰트 (C++)

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

9997번: 폰트

 

 

 

[난이도] Gold2
[유형] 비트마스크

[풀이]
주어지는 단어에 포함된 알파벳을 26자리 비트 int로 변환이 가능합니다.
int로 변환을 해준 뒤에 재귀를 이용해서 만들 수 있는 경우의 수를 모두 조합해주면 됩니다.
현재 단어를 포함 시킬때는 비트or 연산을 이용해 O(1)에 연산이 가능합니다.

 

#include <iostream>
#include <string>
using namespace std;
int N,ans,a[25];
void sol(int n,int b){
    if(n==N) {
        if(b==(1<<26)-1) ans++;
        return;
    }
    sol(n+1,b);
    sol(n+1,b|a[n]);
}
int main(){
    cin >> N;
    for(int i=0;i<N;i++) {
        string s;
        cin >> s;
        int b=0;
        for(auto c : s) b |= (1<<(c-'a'));
        a[i]=b;
    }
    sol(0,0);
    cout << ans;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/9997.cpp