1062 - 가르침

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

k개의 알파벳을 학습하여 N개의 남극언어 중 몇 개를 읽을 수 있는가인데, 시간 복잡도 계산 안하고 그냥 재귀로 돌려봤다 (패기..!)

매번 모든 알파벳을 검사하기는 힘들다. 그리고 어차피 알파벳은 한번만 배우면 계속 쓰일 수 있다. 그럼 각 단어마다 알파벳의 존재여부를 체크하여 저장할 수가 있는데, 한 단어에서 x번째 알파벳이 사용되었다/안되었다(0/1) 로 구분하면 26자리 2진수 (최대 $2^{26}-1$) 로 표현할 수 있다. 그럼 ACE 는 0 00000 00000 00000 00000 10101 로 표현된다.
소스는 1번째...26번째로 해서 비트가 왼쪽으로 하나씩 밀려있다.

A~Z 중에 k개를 선택했을 때 읽을 수 있는 최대 단어의 갯수를 반환하면서, 그 최대값을 갱신하도록 했다.

그리고 "K개의 글자"에 남극언어에 들어가는 ANTA,TICA 도 포함되어야 한다. (이것때문에 한참 틀렸다) 즉, 5개의 글자(ANTIC)를 반드시 배워야한다는 것이다.

#include <bits/stdc++.h>
using namespace std;
 
#define ANTATICA 1065483
 
typedef long long lld;
 
int n, k;
lld words[51];
 
int f(int pos, int alphabet, lld bit){
    if(pos > k || alphabet > 27) return 0;
    if(pos == k){
        int i, cnt=0;
        for(i=0; i<n; ++i){
            cnt += (words[i]&bit) == words[i];
        }
        return cnt;
    }
    int i, r=0;
    for(i=alphabet; i<=26; ++i){
        if((bit&(1<<i))==0){
            r = max(r, f(pos+1, i+1, bit|(1<<i)));
        }
    }
    return r;
}
 
int main(){
    scanf("%d %d ", &n, &k);
    for(int i=0; i<n; ++i){
        char s[16]={};
        scanf("%s ", s);
        int j, len=strlen(s)-4;
        lld hashValue = 1LL;
        for(j=4; j<len; ++j)
            hashValue |= (1<<(s[j]-'a'+1));
        words[i] = hashValue | ANTATICA;
    }
    k -= 5;
    if(k < 0) puts("0");
    else printf("%d", f(0, 1, ANTATICA));
    // antic 의 비트값
    // lld bit = 1LL;
    // bit |= (1<<('a'-'a'+1));
    // bit |= (1<<('n'-'a'+1));
    // bit |= (1<<('t'-'a'+1));
    // bit |= (1<<('i'-'a'+1));
    // bit |= (1<<('c'-'a'+1));
    // printf("%lld", bit);
    return 0;
}