백준 1062 - 가르침

문제 설명

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 단어가 주어지고 K개의 알파벳만 알고 있을 때 읽을 수 있는 단어의 최대 개수를 구하면 된다.

 

우선, 단어의 시작과 끝은 anta와 tica이다.

즉, {a, n, t, i, c}를 모르면 어떠한 단어도 읽을 수 없다.

따라서 K가 5보다 작으면 읽을 수 있는 단어가 없다는 뜻이다.

 

그럼 위의 문자들은 기본적으로 알고 있다고 가정하고 남은 알파벳 중 K-5개를 골라 읽을 수 있는 단어의 개수를 세면 된다.

즉, 조합을 만들듯이 알파벳을 선택하면 된다.

void Dfs(int idx, int depth)
{
    if (depth == K)
    {
        ans = max(ans, CanRead());
    }

    for (int i = idx; i < 26; i++)
    {
        if (learned[i]) continue;

        learned[i] = true;
        Dfs(i + 1, depth + 1);
        learned[i] = false;
    }
}

 

이제 읽을 수 있는 단어의 개수를 세는 CanRead만 구현하면 된다.

이때 bitset을 이용하면 효율적으로 구할 수 있다.

배운 알파벳은 learned에서 관리를 하고 입력받은 단어 역시 bitset으로 저장해 놓는다.

그리고 두 개의 bitset을 AND연산을 수행하고 그 결과가 단어의 1의 개수와 똑같다면 해당 단어는 읽을 수 있는 것이다.

int CanRead()
{
    int cnt = 0;
    for (auto& word : words)
    {
        if ((word & learned).count() == word.count()) cnt++;
    }

    return cnt;
}

 

bitset을 사용하지 않고 배열로 관리를 할 경우와 bitset을 활용한 경우의 속도 차이는 다음과 같다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N, K;
vector<bitset<26>> words;
bitset<26> learned;
int ans = 0;

bitset<26> Convert(string str)
{
    bitset<26> result;

    for (auto c : str)
    {
        result[c - 'a'] = 1;
    }

    return result;
}

int CanRead()
{
    int cnt = 0;
    for (auto& word : words)
    {
        if ((word & learned).count() == word.count()) cnt++;
    }

    return cnt;
}

void Dfs(int idx, int depth)
{
    if (depth == K)
    {
        ans = max(ans, CanRead());
    }

    for (int i = idx; i < 26; i++)
    {
        if (learned[i]) continue;

        learned[i] = true;
        Dfs(i + 1, depth + 1);
        learned[i] = false;
    }
}

int main() 
{
    INPUT_OPTIMIZE;

    cin >> N >> K;
    
    if (K < 5)
    {
        cout << 0;
        return 0;
    }
    
    for (int i = 0; i < N; i++)
    {
        string str;
        cin >> str;
        words.push_back(Convert(str));
    }

    learned['a' - 'a'] = true;
    learned['t' - 'a'] = true;
    learned['i' - 'a'] = true;
    learned['c' - 'a'] = true;
    learned['n' - 'a'] = true;

    Dfs(0, 5);

    cout << ans;

    return 0;
}

---