[Python] 백준 1062 - 가르침 문제 풀이

Overview

BOJ 1062번 가르침 Python 문제 풀이
분류: Backtracking (백트래킹), Bit Manipulation (비트 조작)

---

문제 페이지

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

---

풀이 코드 1 - 백트래킹

from sys import stdin
from itertools import combinations


def main():
    def input():
        return stdin.readline().rstrip()

    n, k = map(int, input().split())
    words = [input()[4:-4] for _ in range(n)]

    learned = {'a', 'n', 't', 'i', 'c'}
    k -= len(learned)

    if k < 0:
        print(0)
        return

    elif k == 21:
        print(n)
        return

    letters = []
    for i in range(26):
        if chr(i + 97) not in learned:
            letters.append(chr(i + 97))

    res = 0
    combs = combinations(letters, k)
    for comb in combs:
        cnt = 0
        for word in words:
            for char in word:
                if char not in comb and char not in learned:
                    break
            else:
                cnt += 1
        res = max(cnt, res)

    print(res)


if __name__ == "__main__":
    main()

채점 결과 pypy3는 통과했지만 python3는 시간초과가 발생하였다.
itertools 라이브러리의 combinations를 이용하여 학습 가능한 모든 경우의 수를 선택하고, 읽을 수 있는 단어 최대 개수를 구한다.

---

풀이 코드 1 - 비트 연산

from sys import stdin
from itertools import combinations


def main():
   def input():
       return stdin.readline().rstrip()

   n, k = map(int, input().split())
   words = [set(input()).difference('a', 'c', 'i', 't', 'n') for _ in range(n)]

   if k < 5:
       print(0)
       return

   letters = {chr(i + 97): i for i in range(26)}
   ids = [i for i in range(26) if chr(i + 97) not in ['a', 'c', 'i', 't', 'n']]

   k -= 5
   res = 0
   for comb in combinations(ids, k):
       mask = 0
       for move in comb:
           mask |= 1 << move

       cnt = 0
       for word in words:
           wordbit = 0
           for char in word:
               wordbit |= 1 << letters[char]
           if mask | wordbit == mask:
               cnt += 1
       res = max(cnt, res)

   print(res)


if __name__ == "__main__":
   main()

단어들과 학습 글자들을 비트로 나타내어 비교하며 읽을 수 있는 단어 최대 개수를 구한다.