🦊 가르침

1. 문제 링크

1062번: 가르침

2. 코드

Python3 31120KB 1660ms

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

words = []
for i in range(N):
    word = input()
    word_bit = 0
    for ch in word:
        word_bit |= 1 << (ord(ch) - ord('a'))
    words.append(word_bit)

learn_count = 0
if K < 5:
    print(0)
elif K == 26:
    print(N)
else:
    learned = 0
    antatica = ['a', 'n', 't', 'i', 'c']
    for ch in antatica:
        learned |= 1 << (ord(ch) - ord('a'))

    def backtracking(n, picked):
        global learned
        global learn_count
        if picked == K:
            count = 0
            for i in range(N):
                if (words[i] & learned) == words[i]:
                    count += 1
            learn_count = max(learn_count, count)
            # print(count)
            return

        # 배움
        for i in range(n, 26):
            to_learn = 1 << i
            if not (learned & to_learn):
                learned |= to_learn
                backtracking(i, picked + 1)
                learned &= ~to_learn

    backtracking(0, 5)
    print(learn_count)

3. 해설

combinations 내장 함수가 너무 느려서 시간초과 발생, 직접 구현하니까 됨

알파벳을 배우는 경우를 int 의 bit 로 마스킹해서 저장

이후 K개의 단어를 배웠을때 비트로 변환한 단어들과 비교해서 배운 여부를 판단