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

 

<조건 분석>

1. "anta"와 "tica"로 끝난다 -> a, n, t, i, c는 무조건 학습해야함.

2. a ~ z 까지의 글자를 학습하는 경우의 수는 각각 '배울까 = 1', '안배울까 = 0' 로 2^26 = 6700만. O(2^26)

 

<문제 해결 포인트>

1. 입력 받는 단어를 비트로 표현하기 ex) "abcabc" = 7

2. 순회하는 알파벳에서 '배울 지', '안배울 지'를 나눠서 재귀

3. 알파벳 a, n, t, i, c는 무조건 학습하게끔 조건 분기

 

 

#include <bits/stdc++.h>
using namespace std;

int N = 0;
int K = 0;
int words[30];

int cal (int bit)
{
    int tmp = 0;
    for (int item : words)
    {
        if (item && ((item & bit) == item)) tmp++;
    }

    return tmp;
}

int go (int index, int count, int bit)
{
    if (count < 0) 
    {
        return 0;
    }
    if (index == 26) 
    {
        return cal(bit);
    }
    int ret = go(index + 1, count - 1, bit | (1 << index));
    if (index != 'a' - 'a' && index != 'n' - 'a' && index != 't' -'a' && index != 'i' - 'a' && index != 'c'- 'a')
    {
        ret = max(ret, go(index + 1, count, bit));
    }
    return ret;

}

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

    cin >> N >> K;

    for (int i = 0; i < N; i++)
    {
        std::string temp;
        cin >> temp;

        for (auto& item : temp)
        {
            words[i] |= (1 << (item - 'a'));
        }
    }

    cout << go (0, K, 0);
}