[BOJ] 백준 1062 가르침

출처: https://www.acmicpc.net/problem/1062

 Input 

3 6

antarctica

antahellotica

antacartica

 

 Output 

2

 

N개의 단어는 모두 아래의 구조를 가지고 있습니다.

[anta]...[tica] 따라서 a, n, t, i, c 알파벳을 알지못하면 모든 단어를 알 수 없습니다.

그렇기에 K < 5이며 알 수 있는 단어의 개수는 0개 입니다.

 

K ≥ 5일때는 a, n, t, i, c 알파벳은 알고있어야 됩니다.

따라서 나머지 알파벳 인지 여부를 통해 알 수 있는 단어의 개수를 파악해야 합니다.

따라서 알파벳을 선택하는 경우의 수는 26-5CK-5

---

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
 
int N, K, answer;
bool alphabet[26];
vector<string> word;
 
int canReadWord(){
    bool isRead;
    int count = 0;
    // 알고 있는 알파벳으로 알 수 있는 단어 개수 확인하기
    for (int i = 0; i < word.size(); i++){
        isRead = true;
        string str = word[i];
        for (int j = 0; j < str.length(); j++){
            if (alphabet[str[j] - 'a'] == false){
                isRead = false;
                break;
            }
        }
 
        if (isRead == true) count++;
    }
    // 완전히 읽을 수 있는 단어 개수 반환
    return count;
}
 
void DFS(int idx, int cnt){
    if (cnt == K){
        int tempAns = canReadWord();
        answer = answer < tempAns ? tempAns : answer;
        return;
    }
 
    for (int i = idx; i < 26; i++){
        // 이미 선택보장된 알파벳은 제외
        if (alphabet[i] == true) continue;
        
        alphabet[i] = true;
        DFS(i, cnt + 1);
        alphabet[i] = false;
    }
}
 
 
int main(){
    cin >> N >> K;
    for (int i = 0; i < N; i++){
        string str;
        cin >> str;
        word.push_back(str);
    }
 
    if(K < 5){
        cout << 0 << endl;
        return 0;
    }
 
    // a, n, t, i, c 알파벳은 선택 보장
    alphabet['a' - 'a'] = true;
    alphabet['n' - 'a'] = true;
    alphabet['t' - 'a'] = true;
    alphabet['i' - 'a'] = true;
    alphabet['c' - 'a'] = true;
    K = K - 5;
 
    DFS(0, 0); // 조합
    cout << answer << endl;
}