[BOJ][C++] 백준 9997번: 폰트

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

 

문제

상근이는 자신이 만든 폰트를 테스트하기 위한 문장을 만들려고 한다. 폰트에는 알파벳 소문자만 포함되어 있기 때문에, 문장은 알파벳 소문자로 작성해야 한다.

테스트 문장에는 알파벳 소문자 26개가 모두 포함되어 있어야 한다.

사실 문제를 많이 풀어본 사람이라면, 문제를 여기까지 읽어도 무슨 문제인지 감이 잡혀야 한다.

상근이는 단어 N개가 포함되어 있는 사전을 하나 가지고 있다. 테스트 문장은 사전에 포함된 단어만 이용해서 만들 수 있으며, 각 단어는 한 번씩만 사용해야 한다. 또, 단어의 순서는 중요하지 않다. (“uvijek jedem sarmu” 와 “jedem sarmu uvijek”는 같은 문장이다)

상근이가 만들 수 있는 테스트 문장의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다.

출력

상근이가 만들 수 있는 테스트 문장의 개수를 출력한다. 

 

풀이

재귀로 모든 경우의 수를 다 따져보면 된다.

 

근데 그 과정에서 비트마스킹을 곁들여서... 

(필자는 본 문제로 비트를 처음 다뤄봤다.. 자세한건 아래 시행착오 참고)

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

int n, ans;
vector<int>words; // words[i] : i번째 단어의 각 알파벳 사용여부를 비트로 저장
vector<bool>usedWord; // usedWord[i] : i번째 단어가 사용되었는가?

void recur(int k, int usedAlphabet) {
    if(k==n-1) {
        if(usedAlphabet == (1<<26)-1) {
            ans++;
        }
        return;
    }
    
    // 다음 단어 포함 안함
    recur(k+1, usedAlphabet);
    
    // 다음 단어 포함
    usedWord[k+1] = true;
    recur(k+1, usedAlphabet|words[k+1]);
    usedWord[k+1] = false;
}

int main() {
    cin >> n;
    words.assign(n, 0);
    usedWord.assign(n, false);
    for(int i=0; i<n; i++) {
        string word;
        cin >> word;
        for(char ch : word) {
            words[i] |= (1 << (ch-'a'));
        }
    }
    
    recur(-1, 0);
    
    cout << ans;
    
    return 0;
}

 

 

시행착오

처음에는 각 단어를 길이가 26인 배열로 저장했다

words[i][j] : i번째 단어가 j번째 알파벳을 가지고 있는가 여부

 

역시 강력하게 오는 시간초과.

재귀로 테스트 문장을 만들때마다 배열을 돌면서 합하고, 

재귀가 끝날 때 마다 문장이 만족하는지 (모든 알파벳이 true인지) 배열을 돌고..

 

어차피 010011101101 이런식으로 저장하게 될텐데

이걸 문자열? 같이 하나로 저장하면 되지 않을까 하는 생각이 들었고

words[i]를 정수로 저장했다. 어차피 이 정수를 이진수로 바꾸면 011011101 이런형태가 되니까.

 

재귀로 테스트 문장을 만들때마다 비트합연산 | 를 하면되고

테스트 문장이 맞는지 검증할때는 2^26-1 (1이 26개)와 같은지만 확인하면 된다

 

비트 연산 엄청 어려운거라고 생각했는데 생각보다 별거 없었던..!

정수 연산이랑 비슷~하다

괜히 이진수, 비트, 이런거 다루니까 전공자 된 것 같고.. 뿌듯함도 두배였음

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

int n, ans;
vector<vector<bool>>words;
vector<bool>usedWord; // usedWord[i] : i번째 단어가 사용되었는가?

bool canTest(vector<bool>&usedAlphabet) {
    for(bool i : usedAlphabet) {
        if(!i) {
            return false;
        }
    }
    return true;
}

void recur(int k, vector<bool>usedAlphabet) {
    if(k==n-1) {
        // 로그
        // for(int i=0; i<n; i++) {
        //     if(usedWord[i]) {
        //         for(int j=0; j<26; j++) {
        //             if(words[i][j]) {
        //                 cout << char(j+'a');
        //             }
        //         }
        //         cout << " ";
        //     }
        // }
        // for(int i=0; i<26; i++) {
        //     cout << usedAlphabet[i];
        // }
        // cout << "\n";
        //
        
        if(canTest(usedAlphabet)) {
            ans++;
        }
        return;
    }
    
    // 다음 단어 포함 안함
    recur(k+1, usedAlphabet);
    
    // 다음 단어 포함
    usedWord[k+1] = true;
    vector<bool>newUsedAlphabet = usedAlphabet;
    for(int i=0; i<26; i++) {
        if(words[k+1][i]) {
            newUsedAlphabet[i] = true;
        }
    }
    recur(k+1, newUsedAlphabet);
    usedWord[k+1] = false;
}

int main() {
    cin >> n;
    words.assign(n, vector<bool>(26, false));
    usedWord.assign(n, false);
    for(int i=0; i<n; i++) {
        string word;
        cin >> word;
        for(char ch : word) {
            words[i][ch-'a'] = true;
        }
    }
    
    recur(-1, vector<bool>(26,false));
    
    cout << ans;
    
    return 0;
}