[백준] 9997 - 폰트

예전 삼성전자 SW Test A형을 딸 때 풀었던 문제랑 비슷해보여서 같은 방법으로 접근했다가 시간초과 났던 문제...

그래서 갯수에 상관없이 비트마스킹 + DFS를 사용하면 되는문제

순서에 상관이 없다는 말이 순서가 바껴도 같은 걸 사용하면 답의 갯수에 추가되는줄 알고 순열로 넣었다가 25!, 아니 예시인 9개에서도 시간초과

그래서 그냥 한 단어를 넣고, 안넣고 두가지 DFS로 문제 해결

#include <iostream>
#include <cstring>
using namespace std;
 
int check[12], visit[12];
char A[102];
int N, com;;
long long dab;
 
void dfs(int d, int sum)
{
    if (d == N - 1)
    {
        if (sum == com) dab++;
        return;
    }
    if (d + 1 < N)
    {
        dfs(d + 1, sum | check[d + 1]);
        dfs(d + 1, sum);
    }
}
 
int main(void)
{
    cin >> N;
    for (int i = 0; i < 26; i++) com |= 1 << i;
 
    for (int i = 0; i < N; i++)
    {
        cin >> A;
        for (int j = 0; j < strlen(A); j++)
            check[i] |= (1<<(A[j] - 'a'));
    }
    dfs(-1, 0);
    cout << dab << endl;
}