[백준] 1062번 : 가르침 - C++

백준 1062 : 가르침

등급 : Gold IV

1062번: 가르침 (acmicpc.net)

1062번: 가르침

사용 알고리즘 : Brute-Force, Backtracking, Bitmasking

사용 자료구조 : Vector

 

백트래킹과 비트마스킹을 적절히 이용하여 풀 수 있는 문제.

탐색 완료를 점검하는 조건에서 코너 케이스가 있어 반례를 찾고 수정하는 데 약간 애를 먹었다.

---

  1. 전체 단어 중 포함된 알파벳을 저장할 배열 chk[26]과, 현재 단어에서 포함된 알파벳을 저장할 배열 p_chk[26] 생성.

       ( 모든 알파벳을 다 검사하지 않고, 나왔던 알파벳만 검사하기 위함 )

  2. 실제로 배워야 할 최대 알파벳 갯수를 저장할 변수 max_learn을 지정하고 초기값은 5로 해준다.

       ( 모든 단어가 anta로 시작하여 tica로 끝나므로 항상 a, c, i, n, t를 배워야 하므로 최소 5. )

  3. a, c, i, n, t에 해당하는 비트인, 0, 2, 8, 13, 19는 항상 포함되어야 하므로 위 숫자를 true로 바꿔주는 light_on 함수 생성.

  4. 비트마스킹 함수 생성.

        1) 인자로 x(현재 체크 횟수), bit(현재 비트), before(이전 알파벳 비트)를 받게 해준다.

           → before를 받는 이유는 이전보다 작은 수가 마킹되는 것을 방지하기 위함이다. (중복 체크 방지)
               ex) 1, 2, 3, 4중 3개를 고르는 방법. : (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), ···

                     이때 순서를 신경 쓸 필요가 없으므로 (1, 2, 3)과 (1, 3, 2)는 동일한 것이 됨.

                     이러한 중복을 막기 위해서는? 전보다 큰 수만 뒤에 올 수 있도록 지정.

                     결과 : (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

        2) x가 k와 max_learn 중 작은 수와 동일할 때, ans값을 계산한다.

           → 본문에서 말한 코너 케이스를 검사하기 위함.

                ex) k=6, antatica인 경우 우리는 나왔던 알파벳만 검사하도록 하였으므로 a, c, i, n, t만 검사할 것이다.

                      이때 모든 것을 다 검사하였음에도 불구하고 k가 남아 x == k인 경우로 갈 수 없게 된다.

                      때문에 최대 가르칠 수 있는 알파벳 수와, 실제 최대로 배워야 하는 알파벳 수를 비교해 더 작은 것일 때 완료되도록 한다.

           → 알파벳 검사의 경우 글자 비트(v)와 최소 학습 비트(bit)를 &연산 했을 때, 글자 비트가 나오면 가능한 것으로 본다.

        3) 완료 조건 이외의 경우, 나왔던 알파벳(chk)이면서 현재 탐색 중에 나오지 않았던 알파벳(p_chk)으로 검사한다.

        4) 참인 경우, 앞서 말한 이전보다 작은 수인지 검사하고, 아닌 경우에 |연산을 통해 현재 알파벳에 해당하는 비트를 추가해준다.

        5) 현재 탐색 중에 나왔던 알파벳(p_chk)이라고 표시해준 뒤, 횟수를 늘려 현재 비트와 알파벳 비트를 인자로 넘겨줌.

        6) 나중에 돌아왔을 때 백트래킹을 수행할 수 있도록 p_chk를 다시 false로 바꿔줌.

  5. n개의 알파벳을 입력받는데, 이때 anta와 tica는 무조건 들어가므로 제외한 부분만 입력받는다.

  6. 기본 비트를 지정해준다. (a, c, i, n, t가 포함되어 있으므로 그 수에 맞는 비트에 1을 표기한 값을 넣는다.)

       (10000010000100000101(2)가 되므로 십진법으로 바꿔주면 532741이 된다.)

  7. 현재 string의 알파벳 갯수를 셀 변수 alpha_cnt를 0으로 초기화해주고, 그에 따라갈 bool변수 amt_chk를 false로 생성.

  8. 입력받은 string들을 검사해주는데, 나왔던 알파벳이 아니라면 chk에 추가해주고 max_learn을 증가시켜준다.

  9. 현재 string에서 나왔던 알파벳이 아니라면 alpha_cnt 검사. 최대 배울 수 있는 양보다 많다면 이 알파벳은 학습 불가.

      그렇지 않다면 alpha_cnt를 늘려주고 현재 string에서 이 알파벳이 나왔음을 체크. 그리고 현재 알파벳을 비트에 추가.

  10. 검사가 모두 끝나고 학습 가능한 단어라면 배열(v)에 추가한다.

  11. 무조건 5글자 이상은 배워야 하기 때문에 k가 5보다 작다면 아무 단어도 만들 수 없으므로 0을 출력.

  12. 그렇지 않다면 지금까지 나온 단어 비트를 가지고 탐색을 시작한다. 이후 결과값 출력.

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool chk[26] = { false };
bool p_chk[26] = { false };
vector <int> v;
int n, k;
int max_learn = 5;
int ans = 0;

void dfs(int x, int bit, int before)
{
    if (x == min(k, max_learn))
    {
        int local_ans = 0;
        for (int i = 0; i < v.size(); i++)
        {
            if ((v[i] & bit) == v[i]) local_ans++;
        }
        ans = max(ans, local_ans);
    }
    else
    {
        for (int i = 1; i < 26; i++)
        {
            if (!p_chk[i] && chk[i])
            {
                int tmp = bit;
                int uni = 1 << i;
                if (before > uni) continue;
                tmp |= uni;
                p_chk[i] = true;
                dfs(x + 1, tmp, uni);
                p_chk[i] = false;
            }
        }
    }
}

void light_on(bool arr[])
{
    arr[0] = true;
    arr[2] = true;
    arr[8] = true;
    arr[13] = true;
    arr[19] = true;
}

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

    cin >> n >> k;
    string str;
    light_on(chk);
    for (int i = 0; i < n; i++)
    {
        cin >> str;
        str = str.substr(4, str.size() - 8);
        int bit = 532741;
        int alpha_cnt = 0;
        bool amt_chk = false;
        fill_n(p_chk, 26, false);
        for (int j = 0; j < str.size(); j++)
        {
            if (!chk[str[j] - 'a'])
            {
                chk[str[j] - 'a'] = true;
                max_learn++;
            }
            if (!p_chk[str[j] - 'a'])
            {
                if (alpha_cnt == k)
                {
                    amt_chk = true;
                    break;
                }
                p_chk[str[j] - 'a'] = true;
                alpha_cnt++;
                bit |= (1 << (str[j] - 'a'));
            }
        }
        if (!amt_chk) v.push_back(bit);
    }
    if (k < 5)
    {
        cout << 0;
        return 0;
    }
    fill_n(p_chk, 26, false);
    light_on(p_chk);
    dfs(5, 532741, 1);
    cout << ans;
}