[백준] No.1062 - 가르침 (C++, 비트마스크)

문제

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

1062번: 가르침

 

풀이

 

solved.ac 난이도: Gold 4

 

이 문제도 비트마스크로 풀었지만 사실 DFS방법의 백트래킹으로도 충분히 시간 내에 해결 가능하다.

또한 본인은 비트마스크와 브루트포스만으로 해결했지만 백트래킹을 같이 활용한다면 훨씬 빠르게 해결이 가능하다.

 

 

남극언어의 단어들은 모두 'a', 'c', 'i', 'n', 't' 를 가져야만 한다.

따라서 비트마스크 표현 시 비트들은 모두 해당 비트를 가져야만 한다.

 

int start_bit = 0;
start_bit |= (1<<('a' - 'a'));
start_bit |= (1<<('c' - 'a'));
start_bit |= (1<<('i' - 'a'));
start_bit |= (1<<('n' - 'a'));
start_bit |= (1<<('t' - 'a'));

 

 

start_bit를 구했다면 단어를 입력받을 때 접두사(?)"anta"와 접미사"tica"이외의 문자만 words_bit에 저장한다.

 

for(int i=0; i<word_num ; ++i){
  cin>>temp;
  words_bits[i] =start_bit;
 
  for(int idx =4 ; idx<(temp.size() - 4 ); ++idx)
    words_bits[i] = words_bits[i] | (1<<(temp[idx] - 'a'));
}

 

이제 bits를 start_bit에서부터 MAX_BIT( = (1<<26 )-1)까지 늘려가며 k개의 글자만 해당 비트가 1로 켜져 있는 조합을 구한다.

이때 bits가 start_bit를 포함하지 않는다면 어떤 단어도 읽을 수 없으므로 

(bits & start_bit) != start_bit 인 bits는 제외시켜준다.

 

켜져있는 비트수(bit_cnt)가 배운 글자 수(learned_num)와 같은 경우만 

단어의 bit표현인 words_bit를 순회하며 읽을 수 있는 단어인지 판단한다.

이때 words_bit와 bits를 AND연산했을 때의 결과가 words_bit라면, if((words_bits[i] & bits) == words_bits[i])

bits는 해당 단어의 모든 글자를, 혹은 그 이상을 포함했다는 것을 알 수 있다.

 

if(bit_cnt == learned_num ){
    for(int i=0; i<word_num ; ++i)
      if((words_bits[i] & bits) == words_bits[i])
        ++pos_word_cnt;

 

26개의 알파벳 중 5개(start_bit)를 제외한 모든 경우의 수는

2^21 = 2,097,152 이므로 시간 안에 충분히 계산 가능하다.

 

이러한 문제처럼 조합을 구하는 문제는 단순 브루트포스에 백트래킹을 활용해서 조합을 구해낼 수도 있다.

 

코드