[1062] 가르침

문제 링크 : https://www.acmicpc.net/problem/1062

1062 - 가르침

본문

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

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

입력

첫째 줄에 단어의 개수 $N$과 $K$가 주어진다. $N$은 $50$보다 작거나 같은 자연수이고, $K$는 $26$보다 작거나 같은 자연수 또는 $0$이다. 둘째 줄부터 $N$개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 $8$보다 크거나 같고, $15$보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 $K$개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

알파벳의 개수는 26개이다. 모든 알파벳에 대해 각 알파벳이 선택되고 선택되지 않고의 조합의 개수는 $2^{26} = 67108864$개가 존재한다. 모든 조합에 대해서 모든 단어를 읽을 수 있는지 판단하는 것은 1초로는 부족할 것 같다. 전체 연산을 1억번 이하로 줄이도록 알고리즘을 구상해보자.

일단 ‘모든 알파벳’에 대해서 조합을 계산하는 것은 개수가 너무 많다. 조합의 개수를 줄이기 위해서는 선택할 필요가 없는 알파벳이 있나 확인해보는 것이 좋다. 이 문제에서는 선택할 필요가 없는 알파벳은 없지만 반대로 반드시 선택되는 알파벳은 존재한다. 개수는 5개 (a, n, t, i, c) 이다. 이것들이 반드시 포함된다고 생각하면 가능한 조합의 개수는 $2^{26-5} = 2097152$개가 된다. 무려 32배나 줄였으니 이정도면 모든 경우를 계산할 수 있을 것 같다.

a, n, t, i, c가 항상 선택되는 모든 조합 (약 210만개) 에 대해서 모든 단어 (최대 50개) 에 대해서 단어의 길이 (최대 15글자) 만큼 검사한다고 가정하면, 최대 연산 횟수는 $1\,575\,000\,000$번, 15.75억번이다. 당연히 1초 안에 계산하는 것은 불가능. 모든 단어에 대해서 계산하는 것은 필수이므로, 단어의 길이를 줄이거나 조합의 개수를 줄이는 방법을 선택해야 문제를 해결할 수 있을 것 같다.

15글자를 1개의 값으로 대표할 수 있는 방법을 찾는다면 연산 횟수를 줄일 수 있을 것이다. 알파벳의 개수는 26개이므로, 알파벳의 사용 여부만 나타내는 비트를 이용하면 단어를 숫자 하나로 표현할 수 있을 것 같다. 모든 단어를 숫자 하나로 표현할 수 있다면 숫자 비교는 and 연산을 통해서 한번에 계산할 수 있으므로, 연산 횟수를 약 1억번으로 줄일 수 있게 된다. 그리고 이것은 1초 안에 돌아갈 가능성이 높으므로, 위 내용들을 구현하여 제출하자.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2024 / 4 / 12

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX 50
#define MAX_LEN 16
const int MINIMUM_ALPHABET = 5;
#define ALPHABET_LEN 26

int n, k;
int word[MAX_IDX];
int result;

char standard[ALPHABET_LEN + 1];

#define max(a, b) (((a) > (b)) ? (a) : (b))

void essential_alphabet_init() {
    char s[10] = "antic";
    for (int i = 0; s[i] != '\0'; ++i) {
        standard[s[i] - 'a'] = true;
    }
    return;
}

void backtrack(int num, int cnt, int pos) {
    if (cnt == k) {
        int temp = 0;
        for (int i = 0; i < n; ++i) {
            if ((num & word[i]) == word[i]) {
                ++temp;
            }
        }
        result = max(result, temp);
        return;
    }

    for (int i = pos; i < ALPHABET_LEN; ++i) {
        if (standard[i] == false) {
            backtrack(num + (1 << i), cnt + 1, i + 1);
        }
    }
    return;
}

int main() {
    essential_alphabet_init();

    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i) {
        char str[MAX_LEN];
        scanf("%s", str);
        for (int j = 0; str[j] != '\0'; ++j) {
            word[i] |= (1 << (str[j] - 'a'));
        }
    }

    if (k < MINIMUM_ALPHABET) {
        printf("0");
        return 0;
    } else {
        int std = 0;
        for (int i = 0; i < ALPHABET_LEN; ++i) {
            if (standard[i] == true) {
                std += (1 << i);
            }
        }

        backtrack(std, MINIMUM_ALPHABET, 0);
    }

    printf("%d", result);
    return 0;
}