[Algorithm] Baekjoon 1062번 : 가르침

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

1062번: 가르침

int n, k;
int chance = 0;
vector<string> targetWords;
vector<char> newAlphabets;
bool m[26] = { false };
int answer = 0;
int maxDepth = 0;
 
void DFS(int index, int depth)
{
    if (depth == maxDepth)
    {
        int answerCount = 0;
        for (int i = 0; i < targetWords.size(); ++i)
        {
            string word = targetWords[i];
            bool check = true;
 
            for (int j = 0; j < word.size(); ++j)
            {
                if (!m[word[j] - 'a'])
                {
                    check = false;
                    break;
                }
            }
 
            if (check) ++answerCount;
        }
 
        answer = max(answer, answerCount);
        return;
    }
 
    for (int i = index + 1; i < newAlphabets.size(); ++i)
    {
        m[newAlphabets[i] - 'a'] = true;
        DFS(i,depth+1);
        m[newAlphabets[i] - 'a'] = false;
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> k;
 
    m['a' - 'a'] = true;
    m['n' - 'a'] = true;
    m['t' - 'a'] = true;
    m['i' - 'a'] = true;
    m['c' - 'a'] = true;
    chance = k - 5;
    bool tm[26];
    memcpy(tm, m, 26);
    int tempAnswer = 0;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
 
        string targetWord = s.substr(4, s.size() - 8);
        string temp = "";
        bool ttm[26];
        memcpy(ttm, m, 26);
 
        for (int k = 0; k < targetWord.size(); ++k)
        {
            if (!ttm[targetWord[k] - 'a']) // a,n,t,c,i 중 하나가 아니라면
            {
                temp += targetWord[k]; // 내가 만들어야 할 문자후보
 
                if (!tm[targetWord[k] - 'a'])
                {
                    newAlphabets.push_back(targetWord[k]);
                    tm[targetWord[k] - 'a'] = true;
                }
            }
        }
 
        if (temp == "") ++tempAnswer;
        else targetWords.push_back(temp);
    }
 
    if (chance < 0)
    {
        cout << 0;
        return 0;
    }
 
    maxDepth = min((int)newAlphabets.size(), chance);
 
    for (int i = 0; i < newAlphabets.size(); ++i)
    {
        m[newAlphabets[i] - 'a'] = true;
        DFS(i,1);
        m[newAlphabets[i] - 'a'] = false;
    }
 
    cout << tempAnswer + answer;
}
 

여타 골드4문제에 비해선 좀 더 어려운 문제.

특히 딱 필요한만큼의 로직을 수행하기위해 전처리하는 과정이 필요하다.

그리고 알파벳 사용여부는 map대신 아스키코드값을 인덱스로 이용한 bool배열로 하는게 좋다.

map으로 해도 통과는 한다만, 굳이 한번의 접근으로 값을 알 수 있는 bool배열을 두고 해쉬맵을 사용할 필요는 없기 때문이다.