9997번

9997번 - 폰트

로직.

비트마스크를 이용해서 단어에 어떤 알파벳이 쓰였는지 p 배열에 저장한다.

모든 p배열 전체집합의 부분집합을 구하고, 그 부분집합의 p 배열들의 알파벳 값을 모두 구한다.

그 값이 모든 알파벳이 쓰여진 이진수 (1<<26) - 1과 같으면 갯수를 올려준다.

##

처음에는 dfs 함수에서 sum 값을 사용하지 않고, k==n 일때 for문을 사용해서 하니까 시간초과가 발생했다.

또 dfs를 사용하지 않고, 비트마스크만을 이용해서 구해도 시간초과가 발생했다.

아무래도 재귀함수를 이용하면, sum 값이 초기화 되지 않고 계속 연속적으로 구할 수 있다보니 더 유용했다.

<정답 코드>

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int n;
int op[30];
int ans = 0;
void dfs(int k, int sum, vector<int> &p)
{
    if (k == n)
    {
        int goal = (1 << 26) - 1;
 
 
        if (sum == goal)
        {
            ans++;
        }
 
        return;
    }
 
    dfs(k + 1,sum | p[k], p);
    dfs(k + 1,sum, p);
 
 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    cin >> n;
    vector<string> v(n);
    vector<int> p(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        for (int j = 0; j < v[i].size(); j++)
        {
            p[i] |= (1 << (v[i][j] - 'a'));
        }
    }
 
    dfs(0,0,p);
 
    cout << ans << endl;
 
    return 0;
}