가르침

문제

남극의 언어는 anta로 시작되고 tica로 끝난다.
학생들에게 K개의 알파벳을 가르친다고 할때 최대 몇개의 단어를 학생이 읽을 수 있는지 구하는 문제

제약조건
단어의 개수 N, 1 <= N <= 50
단어는 중복이 없다.
8 <= 단어의 길이 <= 15

가르칠 알파벳의 수 K, 0 <= K < 26

단어는 알파벳 소문자로 이루어져있다.

풀이

남극의 언어는 anta로 시작하고 tica로 끝난다는 말은 a,t,i,c,n에 대한 교육이 없다면 남극의 어떤 단어도 읽을수 없다는 뜻이다. => 0을 반환한다.

알파벳 글자수는 총 26개이므로 가르친 알파벳의 수가 26이면 모든 글자를 다 읽을 수 있다. => N을 반환한다.

알파벳 글자수는 26개이다. 2^26으로 특정 알파벳을 배웠는지 배우지 않았는지를 비트로 나타낼수있다. 크기 / 수행시간 / 코드가 짧기 때문에 비트로 표현시에 이득이 있다.

1. learned라는 변수에 가르친 알파벳을 비트로 저장한다. 다음과 같이 저장 가능하다.
   learned |= 1 << (ord(알파벳)-ord('a'))
   (or 연산자이므로 가르친 알파벳에 대한 비트를 1로 만들 수 있다.)
   a,t,i,c,n에 대한 교육은 필수이므로 해당 알파벳들을 가르킨다.

2. 같은 방법으로 각 단어를 비트로 변환한다. 단어를 set으로 처리하고 비트연산하면 알파벳에 대한 중복이 제거 된다.

3. 함수를 정의한다. dfs(alphabet, learned_N, learned)
   : 현재 알파벳을(alphabet) 가르치거나 가르치지 않았을때 최대 읽을 수있는 단어를 반환한다. = dfs(가르칠 알파벳, 가르친 알파벳의 개수, 비트로 표현된 가르친 알파벳)

4. 함수의 내부는 다음과 같다.

• 가르친 글자수가 K와 같은 경우.
  더 이상 가르칠수 없으므로 모든 단어에 대해 다음과 같은 연산을 실행하고 true일 경우의 갯수를 샌다. learned & word == word
  간단하게 말해서 현재 가르친 단어가 a,b,c,d이라면
  learned는 11110000000000000000000000 으로 표현된다.
  word가 만약에 ab라면 11000000000000000000000000로 표현될것이고 둘을 and연산하게 되면 11000000000000000000000000가 나온다. 즉 'abcd비트표현'&'ab비트표현' == 'ab비트표현'이므로 abcd를 가르쳤을때 ab를 읽을 수 있다.

• 가르쳐야할 글자수가 현재 알파벳을 포함한 남은 알파벳의 수보다 작은 경우 현재 알파벳을 포함 남은 알파벳을 모두 가르쳐도 K개를 가르칠수없으므로 K개를 가르키는 경우에 포함된다. 따라서 가지치기를 위해 -1을 반환한다.

• 이미 가르친 알파벳이라면 다음 알파벳으로 스킵한다.

• 현재 알파벳을 가르치는 경우 / 가르치지 않는 경우로 함수를 나누어 재귀 호출하고 값을 얻은 뒤 max값을 반환한다.
  return max(dfs(alphabet+1, learned_N+1, learned | (1 << alphabet)), dfs(alphabet+1, learned_N, learned))

코드

'''
Created by jun on 21/05/29
'''
#고를 수있는 인덱스.
#학습된 결과와 word와의 and연산이 word와 같다면 해당 word는 학습으로 읽을 수 있는 단어이다.
#현재알파벳, 가르친 단어수, 가르친 단어(bit)
def dfs(alphabet, learned_N, learned):
    #가르친 단어수가 K인 경우.
    if(learned_N == K):
        #가르친 단어수에 따른 읽을수있는 단어수를 계산한다.
        cnt = 0
        for word in words:
            if word == (word & learned):
                cnt += 1
        return cnt

    #가르쳐야할 단어의 수가(K - learned_N). 현재 알파벳을 포함해서
    #남은 알파벳 수보다 많다면 -1을 리턴한다.
    #이거 안해주면 시간초과. 아마 생각외로 함수의 갯수를 많이 줄여주는것같음.
    if(K - learned_N > 26 - alphabet):
        return -1

    #알파벳이 Z를 넘어가면 선택 불가능하다.
    if(alphabet == 26):
        return -1

    #이미 가르친 경우 다음으로 넘어간다.
    if(learned_N & (1 << alphabet) == alphabet):
        return dfs(alphabet+1, learned_N, learned)

    #현재 알파벳을 가르치는 경우 / 가르치지 않는 경우
    return max(dfs(alphabet+1, learned_N+1, learned | (1 << alphabet)), dfs(alphabet+1, learned_N, learned))


N, K = map(int, input().split())

#word를 비트로 표현한다.
words = []
for _ in range(N):
    word = 0
    for char in input():
        word |= 1 << (ord(char)-ord('a'))
    words.append(word)

#학습된 결과이다.
learned = 0
#a,n,t,i,c 을 학습시킨다.
learned |= 1 << (ord('a')-ord('a'))
learned |= 1 << (ord('n')-ord('a'))
learned |= 1 << (ord('t')-ord('a'))
learned |= 1 << (ord('i')-ord('a'))
learned |= 1 << (ord('c')-ord('a'))

if K == 26:#K가 26이라면, 모든 영단어를 다 읽을수있는 것이다.
    print(N)
elif K < 5:#K가 5미만이라면, 모든 영단어를 다 읽을수없는 것이다.
    print(0)
else:#이외의 경우 브루트포스를 통해서 결과를 구한다.
    print(dfs(0, 5, learned))


#https://ooyoung.tistory.com/104
#https://onlytrying.tistory.com/154

새로 알게된 사실

비트마스킹의 사용법.