[ 백준 1062 ] 가르침 (C++)

백준의 가르침(1062) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 백준에서 시뮬레이션으로 분류되어 있지만, 시뮬레이션도 맞지만 사실 브루트포스 혹은 백트래킹 문제가 더 맞

   는 것 같다. 문제를 다시 요약해보면, 남극에 사는 아이들에게 최대한 많은 단어를 가르치기 위해서 정해진 갯수만큼의

   알파벳만 가르칠 수 있을 떄, 주어진 단어중에서 몇개를 아이들이 읽을 수 있는지 구하는 문제이다.

2) 먼저, 문제에서 주어진 첫 번쨰 조건을 잘 살펴보자. "남극의 단어는 "anta"로 시작해서 "tica"로 끝난다." 라는 조건이

   있다. 즉, 'a' . 'n' , 't' , 'i', 'c' 중에서 하나라도 배우지 못한다면 그 어떠한 단어도 읽지 못한다는 것이다.

   즉, 가르칠 수 있는 단어의 갯수인 K가 5보다 작은 값이 입력이 되면, 그 어떠한 단어도 읽지 못하게 된다.

3) 그렇다면 배웠고 배우지 못한 알파벳들을 어떻게 표시해줘야 할까?? 본인은 Alphabet[] 이라는 1차원 bool형 배열을

   사용하였다. 즉, a를 배웠다면, Alphabet[0] = true, c를 배웠다면, Alphabet[2] = true 이런식으로 알파벳을 숫자로

   매칭시켜서 해당 인덱스의 값을 true로 바꿔주었다.

   여기서 주의해야 할 점은 a n t i c 이 5개의 알파벳은 시작부터 true로 설정해줘야 한다는 것이다. 만약, 저 5개의 알파벳중

   하나라도 배우지 못한다면 읽을 수 있는 단어가 없기 떄문이다.

   이 후, 알파벳에서 K-5개의 알파벳을 조합을 뽑듯이 뽑아주면 된다.

   조합인이유는 , a b c 3개의 알파벳을 알고 있을 때와, b c a 3개의 알파벳을 알고 있을 때, 읽을 수 있는 단어는 똑같기

   때문이다. 즉, 무슨 알파벳을 알고있냐에 따른 순서가 의미가 없기 떄문에 조합을 구현해 주면 된다.

   조합을 잘 모른다면 아래의 글을 참고해보도록 하자.

   [ 조합 구현하기(Click) ]

4) 조합을 모두 구현했다면, 이제는 읽을 수 있는 단어의 갯수를 Count해야 한다. 읽을 수 있는 단어인지 아닌지 판단하는

   방법에 대해서 알아보자.

   "abcde" 라는 단어가 있다고 가정해보자. 그렇다면, a~e까지 5개의 문자에 대해서 반복하면서 , 현재 그 문자의 값이

   false로 설정되어 있다면, 배우지 않았다는 것을 의미하고, 그 단어는 읽을 수 없는 것이라 판단하면 된다.

   즉, false에 한번도 걸리지 않는 단어들은 읽을 수 있다고 판단하면 된다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
 
#define endl "\n"
using namespace std;
 
int N, K, Answer;
bool Alphabet[26];
vector<string> V;
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    // a n t i c 가 무조건 들어가
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        string Inp; cin >> Inp;
        V.push_back(Inp);
    }
 
    if (K < 5)
    {
        cout << 0 << endl;
        exit(0);
    }
}
 
int CanReadNum()
{
    bool Read;
    int Cnt = 0;
    for (int i = 0; i < V.size(); i++)
    {
        Read = true;
        string str = V[i];
        for (int j = 0; j < str.length(); j++)
        {
            if (Alphabet[str[j] - 'a'] == false)
            {
                Read = false;
                break;
            }
        }
 
        if (Read == true)
        {
            Cnt++;
        }
    }
    return Cnt;
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == K)
    {
        Answer = Bigger(Answer, CanReadNum());
        return;
    }
 
    for (int i = Idx; i < 26; i++)
    {
        if (Alphabet[i] == true) continue;
        Alphabet[i] = true;
        DFS(i, Cnt + 1);
        Alphabet[i] = false;
    }
}
 
void Solution()
{
    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;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}