BOJ 1062 : 가르침

문제링크

풀이요약

비트마스킹, 백트래킹

풀이상세

1. 먼저 예외부터 정리하자. $K<5$ 이하인 경우는 단어를 배울 수 없다. 모든 남극의 단어는 anta~tica 의 형태이며, a, n ,t ,i ,c 의 단어는 무조건 알아야 단어를 배우는 것이 가능하다. 반대로 표현하자면 $K < 5$ 보다 작은 경우는 탐색 할 필요없이 $0$ 을 출력하면 된다.

2. 어떤 단어든 a, n, t, i, c 를 배운다. 즉 5개는 먼저 배운상태로 진행해도 탐색에 지장을 주지 않는다. 위의 5문자를 알파벳 문자열 순서로 이진화하면, $532741$ 이 나온다.

3. 부분집합으로도 정답은 나오겠지만 26 개 정도의 부분집합은 분명 시간초과가 나올 수 밖에 없다. 정답이 나오는 요소는 $K$ 만큼 문자를 아는 것이 가장 단어를 많이 알 수 있는 것에 가깝기 때문에 여기서는 조합을 사용하는 것이 좋다.

4. 현재 알파벳이 포함되어 있는 경우를 제외하고, 포함하지 않는 경우의 문자만 하나씩 추가하여 조합을 진행한다. 단, 보다 빠른 계산을 위해 초기 시작값을 a, n, t, i, c 를 이미 가지고 시작하는 것으로 했다.

5. 임의의 $K$ 개 만큼 알파벳을 알고 있을 때, 현재 문자를 아는지 모르는지 판별하는 방법은 두개의 정수를 이진화하여 비교했을 때, 하나의 정수와 값이 완전 일치할 때 이다. (curr & a[i]) == a[i] , (curr | a[i]) == curr

배운점

• 좀 더 빠른 처리를 위해 $t$ 의 값을 만들었다. $t$ 는 임의의 테스트케이스에 등장하는 모든 문자를 가지고 있도록 했다. 즉 $t$ 와 비교시 반영되지 않는 알파벳은 탐색하지 않게 하기 위한 용도로 만들었으나, 틀렸다고 나온다. 왜그럴까?

#include <iostream>
#include <vector>

using namespace std;
int N, K, a[51],ans;
//int t

void input() {
    string s;
    for (int i = 0; i < N; i++) {
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            int num = (1 << (int) (s[j] - 'a'));
            a[i] |= a[i] & num ? 0 : num;
						// t |= t & num ? 0 : num;
        }
    }
}

void solve(int d, int idx, int curr) {
    if (d >= K) {
        int cnt = 0;
        for (int i = 0; i < N; i++) if ((curr & a[i]) == a[i]) cnt++;
        ans = max(ans, cnt);
        return;
    }
    for (int i = idx; i < 26; i++) {
        int num = 1 << i;
        if (curr & num) continue;
				//if (!(t & num)) continue;
        solve(d + 1, i + 1, curr | num);
    }
}

void output() {
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> K;
    if (K < 5) {
        cout << 0;
        return 0;
    }
    input();
    solve(5, 0, 532741);
    output();
}