[백준 1062] 가르침

처음에는 그리디로 접근했다.

하지만 그리디로 접근하면 안된다.

그럼 DP?

→ 말이 안된다.

 

이 문제는 anta 랑 tica를 뺀 중간 단어들을 가장 많이 만들 수 있게 해주는 알파벳 N개를 선택하는 것인데,

이때 가장 빈도수가 높은 알파벳 N개를 선택하면 안된다.

 

예를 들어 antic에 포함안되어있는 단어 중 b랑 d가 두번씩 나왔는데 b는 ban 이라 b만 있으면 만들 수 있는 반면

d는 dxy라 d가 빈도수 높게 나왔어도 못만들기 때문이다.

이렇게 xy까지 필요한 d보다 빈도수가 한번인 n이라는 단어 하나 만드는게 더 낫기 때문이다.

따라서 그리디로 풀면 못푼다

 

따라서 N이 50으로 제한되어있고 알파벳도 26개로 제한되어있는 것을 힌트삼아

걍 죄다 때려박아보는 브루트포스 방식을 생각해보게 되었고

기존 알파벳으로 특정 단어의 생성가능여부를 좀 더 쉽게 확인하기 위해 bitset과 & 비트연산을 사용해 풀었다.

 

사실 백준풀때 무식한 브루트포스보다는 그리디 DP 그래프이론 이런 로직적인 부분을 생각하고 들어가기에

풀면서도 이게 과연 맞는 것일까 한편으로는 고민이 되었다.

 

근데 재귀로 브루트포스 돌려도 1초 안에는 해결할 수 있을 것 같아 일단 질러봄.

 

근데 웬걸 진짜 브루트포스 + 비트마스킹 문제였네,,,

---

#include <iostream>
#include <vector>
#include <bitset>

#define SIZE 50

using namespace std;

int N, K;
// 가로 26 세로 50개 단어
bitset<26> words[SIZE];
int ans = 0;

void check(bitset<26> visited)
{
    int cnt = 0;
    for (int i = 0; i < N; i++)
    {
        if ((visited & words[i]) == words[i])
        {
            cnt++;
        }
    }

    if (cnt > ans)
    {
        // for (int i = 0; i < 26; i++)
        // {
        //     if (visited[i])
        //     {
        //         char ch = 'a' + i;
        //         cout << ch << " ";
        //     }
        // }
        // cout << "\n";
        ans = cnt;
    }
}

void dfs(int cur, int cnt, bitset<26> visited)
{
    // 가르칠 수 있는 갯수를 채웠거나
    // 이미 모든 단어를 다 읽을 수 있으면
    if (cnt == K || visited.count() == 26)
    {
        check(visited);
        return;
    }

    for (int i = cur + 1; i < 26; i++)
    {
        if (!visited[i])
        {
            visited[i] = 1;
            dfs(i, cnt + 1, visited);
            visited[i] = 0;
        }
    }
}

void solve()
{
    bitset<26> visited;
    char arr[] = {'a', 'n', 't', 'i', 'c'};
    for (int i = 0; i < 5; i++)
    {
        visited[arr[i] - 'a'] = 1;
    }

    // 이미 5개는 채워졌으니 cnt는 5로 박고 시작
    dfs(0, 5, visited);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;

    string s;
    for (int i = 0; i < N; i++)
    {
        cin >> s;
        for (int k = 0; k < s.size(); k++)
        {
            words[i][s[k] - 'a'] = 1;
        }
    }

    // 5개도 못읽으면 아무것도 못읽음
    if (K < 5)
    {
        cout << "0";
        return 0;
    }

    solve();

    cout << ans;

    return 0;
}