# 1062. 가르침

관련 알고리즘 : 브루트포스, 재귀, dfs, 비트마스킹

비트마스킹으로는 못 풀어봐서 다음에 비트마스킹으로도 풀어봐야겠다.

 

문제 링크 : https://www.acmicpc.net/problem/1062

1062번: 가르침

---

해결 과정

 

김지민 선생님이 k 개의 글자를 학생들에게 가르치고, 학생들은 k개의 글자만 읽을 수 있다.

 

그런데 남극의 모든 단어들은 "anta"로 시작하고, "tica"로 끝나기 때문에 학생들이 남극의 단어들을 읽을 수 있으려면

a, c, i, n, t 이 5개의 알파벳을 배웠어야 한다.

=> 배운 k개의 알파벳들 중 5개를 뺀 (k-5)개의 알파벳들을 이용해 읽을 수 있는 단어의 최댓값을 찾아야 한다. (k > 5)

 

• 예시 1

3 6
anta// rc //tica
anta// hello //tica
anta// car //tica

n = 3, k = 6이므로

k-5 = 6 - 5= 1

a, c, i, n, t를 제외한 1개의 단어만 읽을 수 있다.

anta부분과 tica부분을 제외한 가운데 단어 부분에서 가장 많이 겹치는 단어를 찾으면 r이므로, 

예시1 에서는 최대 2개의 단어를 읽을 수 있다.

 

알파벳은 총 26개가 존재하므로,

1. 5개의 알파벳을 제외한 21개의 알파벳들의 조합을 구해(21
2. dfs와 재귀를 이용, 각 단어마다 읽을 수 있는지 없는지 여부를 검사 후
3. 최대 개수를 카운트해주면 된다.

또, 5개 이하로 알파벳을 배운 경우 (k < 5인 경우)

모든 단어를 읽을 수 없으므로 0을 반환한다.

 

C++을 이용해 조합을 구하는 방법은 https://yabmoons.tistory.com/99 를 참고하면 좋을 듯 하다.

---

C++ 코드

 

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int n; // 단어 개수
int k; // 배운 알파벳 개수
int res; // 읽을 수 있는 단어개수(결과값)
bool v[26];
string s;
string word[50];

void solve(char c, int cnt)
{
    if (cnt == k - 5)
    {
        int sum = 0; // 읽을 수 있는 단어 개수
        for (int i = 0; i < n; i++)
        {
            bool check = true; // 읽을 수 있는 단어인지
            for (int j = 0; j < word[i].size(); j++) // 단어 한글자씩 돌면서
            {
                if (!v[word[i][j]-'a']) // 읽을 수 없는 단어가 한글자라도 있으면
                {
                    check = false; // false 반환
                    break;
                }
            }
            if (check) sum++; // 모두 다 읽을 수 있는 글자라면 결과값에 추가
        }

        res = max(sum, res); // 조합의 이전 결과값과 비교, res의 최대값 갱신
        return;
    }

    for (int i = c; i < 26; i++) // 알파벳 조합 만들기
    {
        if (!v[i])
        {
            v[i] = true;
            solve(i, cnt+1);
            v[i] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        string cut;
        cin >> cut;
        cut.erase(0,4); // anta 부분 자르기
        cut.erase(cut.size()-4, cut.size()); // tica 부분 자르기
        word[i] = cut;
    }

    if (k < 5) // antic 5글자 모두 모를때
    {
        cout << 0 << '\n'; // 0 반환
        return 0;
    }
	
    // 5글자 이상일 때, a, n, t, i, c는 모두 이미 아는 상태
    v['a' - 'a'] = true;
    v['n' - 'a'] = true;
    v['t' - 'a'] = true;
    v['i' - 'a'] = true;
    v['c' - 'a'] = true;

    solve(0,0);
    
    cout << res << '\n';
}