초기 아이디어
조합이 가장 먼저 떠올랐다. 알파벳 스물여섯개 중 주어진 숫자만큼 조합으로 이용해서 뽑고, 단어마다 해당 단어가 뽑은 단어에 포함되어 있는지를 셈해보는 것이다. 최악의 경우 21C10 의 경우의 수에 각각 50개의 단어를 판별해야 한다. (acnti 다섯글자는 반드시 있어야 하므로) 대충 보면 시간 초과가 날 것 같진 않은데 ... 비슷한 문제를 재귀를 이용한 조합으로 단순히 풀었다가 시간 초과가 난 기억이 있어서 그냥 비트마스킹 연습도 할겸 비트마스킹으로 풀어보기로 한다.
비트마스킹은 사실 근본적인 알고리즘이라기 스킬의 일종이다. 이진법으로 나타낸 수의 각 자리를 하나의 불리언이라고 생각하고 특정 조합을 하나의 숫자로 나타내는 것이다. 예컨대 13을 이진수로 표현하면 1101 인데 '첫번째, 두번째, 네번째만 선택하고 3번째는 선택하지 않는다' 라는 조합으로 인식할 수 있다는 것이다. 이때 비트연산자 ~, ^, &, |, <<, >> 를 이용해서 하는 연산이 여러가지가 있는데, 이걸 외워두는게 상당히 번거롭고 휘발성도 강하다... 연습이 많이 필요하다.
간단한 활용법을 몇개 적어둔다.
i 번째 비트 켜기 : mask |= (1<<i)
i 번째 비트 끄기 : mask &= ~(1 << i)
i 번째 비트가 켜져있는지 확인 : if(mask & (1 << i))
문제 풀이
#include<bits/stdc++.h>
using namespace std;
int n, m, word[51];
int mask;
int count(int mask){
int cnt = 0;
for(int i=0;i<n;i++){
if((word[i] & mask) == word[i]) cnt ++;
}
return cnt;
}
int combi(int idx, int m, int mask){
if(m < 0) return 0;
if(idx == 26) return count(mask);
int ret = combi(idx+1, m-1, mask|(1 << idx));
if(!(idx=='a' - 'a'||idx=='n'-'a'||idx=='t'-'a'||idx=='i'-'a'||idx=='c'-'a')){
ret = max(ret, combi(idx+1, m, mask));
}
return ret;
}
int main(){
cin >> n >> m;
string s;
for(int i=0;i<n;i++){
cin >> s;
for(char c:s){
word[i] |= (1 << (c-'a'));
}
}
cout << combi(0, m, 0);
}보면 재귀를 이용한 조합이라는 알고리즘 형태는 똑같다. 알파벳 단어를 조합하는 형태가 비트마스킹일 뿐이다.
if((word[i] & mask) == word[i]) cnt ++;
이 부분이 조금 헷갈릴 수 있는데, word 가 mask 와 & 연산을 했을 시에 mask 가 word 의 알파벳 자리가 마스킹이 되어 있으면(1이면) 그대로 1 을 반환하고 가지고 있지 않으면 해당자리가 0 이 되는 것을 활용한 수식이다.
