백준 1062 가르침

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

1062번: 가르침

풀이

학생들에게 알파벳 a ~ z 중에서 K개를 가르칠 수 있습니다.

하지만 모든 단어의 앞에는 anta , 뒤에는 tica가 붙습니다.

그렇기 때문에 'a' , 't' , 'n' , 'i' , 'c' 는 모두 무조건 알아야됩니다.

 

만약 K가 5미만이라면 위의 알파벳을 모두 알려줄 수 없습니다.

그렇기 때문에 K가 5미만이라면 값은 무조건 0입니다.

 

만약 K가 5이상이라면 

 

'a' , 't' , 'n' , 'i' , 'c' 는 이미 가르쳤다고 가정후

위의 알파벳을 제외한 나머지 알파벳을 가르켜주는 경우의 수는 최대 max(₂₁C₁, ₂₁C₂ ... ₂₁C₂₁)  = 352716이고 

주어지는 단어의 갯수는 N개(최대 50)

단어의 길이는 ('a' , 't' , 'n' , 'i' , 'c')를 제외하면 (최대 7)

 

브루트포스로 모든 경우를 고려했을 경우 최악의 경우를 가정하면

352716 × 50 × 7 = 123,450,600 만큼 걸립니다.

아슬아슬하게 1초만에 통과할수 있는 수치임을 확인했음으로 브루트포스로 모든 경우를 고려하면 됩니다.

 

저는 DFS 이용해서 알파벳을 배울 수 있는 모든 경우의 수를 고려했습니다.

시간을 더욱 확실하게 줄이기 위해서 비트마스킹을 사용해서 단어검사 시간을 줄였습니다.

352716 × 50 = 17,635,800 로 시간복잡도를 줄였습니다.

 

 

자세한것은 코드를 참조해주세요!!

 

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

int N, K;
const int MAX = 21;
vector<int> stringBit;
int nowBit = 0;
int result = 0;

void DFS(int a, int b)
{
    if (b == 0)
    {
        int ans = 0;
        //현재 상태에서 몇개의 단어를 읽을 수 있는지 검사
        for (int i = 0; i < N; i++)
            if ((stringBit[i] & nowBit) == stringBit[i])
                ans++;
        result = max(result, ans);
        return;
    }

    nowBit |= (1 << (a - 1));
    if (b == 1)
        DFS(a, 0);
    else
        for (int i = a + 1; i <= MAX - b + 2; i++)
            DFS(i, b - 1);
    nowBit -= (1 << (a - 1));

}

int GetAlphaBit(char c)
{
    int i = (c - 'a');
    if (c < 'c')
        return i - 1;
    else if (c < 'i')
        return i - 2;
    else if (c < 'n')
        return i - 3;
    else if (c < 't')
        return i - 4;
    else
        return i - 5;
}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        string s;
        cin >> s;

        //해당 문자열이 필요한 알파벳을 비트마스킹을 이용해서 표현
        int tempBit = 0;
        for (int j = 0; j < s.length(); j++)
            if (s[j] != 'a' && s[j] != 't' && s[j] != 'n' && s[j] != 'i' && s[j] != 'c')
                tempBit |= (1 << GetAlphaBit(s[j]));
        stringBit.push_back(tempBit);
    }

    //'a', 't', 'n', 'i', 'c'를 모두 못 읽는다.
    if (K < 5)
    {
        cout << 0 << endl;
        return 0;
    }

	//21C(k-5)에 해당하는 경우의 수를 모두 탐색

    DFS(0, K - 4);

    cout << result << endl;
}

 

-----------------------------------------------------------------------------------------------------------------------------------

질문은 언제나 환영합니다.