[9997] 폰트

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

N개의 단어가 주어졌을 때

이 단어들의 조합으로 a-z까지의 알파벳을 한 번씩 사용하는 문장을 몇 개 만들 수 있는지를 묻는 문제이다.

단어들은 한 번씩만 사용할 수 있다.

예) abcd efgh ijkl mnop qrst uvwxyz 라는 단어들이 주어졌을 때

이 단어들을 모두 한 번씩 사용하면 a-z까지의 알파벳을 모두 한 번씩 사용하게 되므로

상근이가 만들 수 있는 테스트 문장의 개수는 1개이다.

나는 비트 마스크를 이용하여 풀었다.

먼저 시프트 연산을 통해 각 단어의 값을 저장한다.

각 알파벳의 값이 비트의 한 자리씩 담당하게 된다.

예를 들어 단어가 'abc'이고 단어를 저장하는 변수가 str, 단어의 값을 저장할 변수가 sum이라 했을 때(초깃값 0)

sum |= (1<<(str[0] - 'a'));

sum |= (1<<(str[1] - 'a'));

sum |= (1<<(str[2] - 'a'));

로 단어의 값을 표현할 수 있다.

- 'a' 를 하는 이유는 아스키코드 값으로 볼 때 영어 소문자에서 a를 빼준다면 각 알파벳은 a = 0, ..., z = 25의 값을 가지게 되기 때문이다

  (cba)

이렇게 하면 abc는 ...000111이라는 값이 되고 int형으로 sum에 저장했을 때 7이라는 값이 된다.

그 후 각 단어를 조합해 a-z까지 한 번씩만 사용했을 때의 값((1 << 26) -1)과 같아지는 값이 있으면

현재 문장이 테스트 문장이라고 볼 수 있다.

조합을 찾는 건 완전탐색을 이용하면 될 것 같아 재귀를 이용했다.

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int alphaSum = (1 << 26) - 1;
int res;
 
void func(int pos, int sum, int n, vector<int> &a) {
    if (pos == n) {
        if (sum == alphaSum) res++;
        return;
    }
    func(pos + 1, sum, n, a);
    func(pos + 1, sum | a[pos], n, a);
}
 
int main() {
    int n;
    vector<string> input;
    vector<int> alpha;
    string a;
    scanf("%d", &n);
    for (int i = 0; i<n; i++) {
        cin >> a;
        input.push_back(a);
    }
 
    for (int i = 0; i<(int)input.size(); i++) {
        int sum = 0;
        for (int j = 0; j<(int)input[i].size(); j++) {
            sum |= (1 << (input[i][j] - 'a'));
        }
        alpha.push_back(sum);
    }
 
    func(0, 0, n, alpha);
 
    printf("%d\n", res);
 
    return 0;
}