백준 1062 - 가르침 (파이썬)

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

풀이

1. 문제 분석

• 주어진 N개의 단어는 항상 “anta” 로 시작하고, “tica” 로 끝난다.
• 따라서 ‘a’, ‘c’, ‘i’, ‘n’, ‘t’ 다섯 개의 글자는 반드시 알아야 한다.
• 만약 K < 5라면, 기본적으로 필수 글자 5개도 배울 수 없으므로 어떤 단어도 읽을 수 없기 때문에 답은 0이 된다.
• K-5개의 추가 글자를 선택하여, 최대 몇 개의 단어를 읽을 수 있는지 탐색해야 한다.

1. 해결 방법
   1. 기본 글자 (‘a’, ‘c’, ‘i’, ‘n’, ‘t’)를 제외한 21개의 글자 중 K-5개 선택
      • itertools.combinations을 사용하여 K-5개의 글자 조합을 만듬
   2. 각 조합에 대해 읽을 수 있는 단어 개수 계산
      • 선택한 글자로 단어를 읽을 수 있는지 확인하고, 최대 개수를 갱신
   3. 백트래킹을 사용하여 탐색 최적화
      • 선택한 조합에 대해 teach 배열을 갱신하고, 다시 되돌리는 과정
2. 시간 복잡도 분석
   • words에는 최대 21개의 문자가 남아 있음.
   • K-5개의 문자를 선택하는 경우의 수는 C(21, K-5).
   • 최악의 경우 C(21, 10) ≈ 352716 (약 35만 개)
   • 각 조합마다 N개의 단어를 확인하는데, 단어의 길이는 최대 15 (최악의 경우 15번 비교).
   • 총 연산량 ≈ 352716 × N × 15
   • N이 50이라면 약 2.6억 번의 연산 → 브루트포스 접근이 가능!

코드

# 백준 1062 - 가르침
# 분류 : 브루트포스 알고리즘, 백트래킹

from itertools import combinations

N, K = map(int, input().split())
V = []

for _ in range(N) :
    V.append(input()[4:-4])

if K < 5 :
    print(0)
else :
    def solve(V, teach) :
        count = 0
        for voca in V :
            possible = True
            for word in voca :
                if not teach[ord(word) - ord('a')] :
                    possible = False
                    break
            if possible == True :
                count += 1
        return count
    
    words = []
    for i in range(26) :
        if chr(ord('a') + i) in ['a', 'c', 'i', 'n', 't'] :
            continue
        words.append(chr(ord('a') + i))

    teach = [False]  * 26
    for a in ['a', 'c', 'i', 'n', 't'] :
        teach[ord(a) - ord('a')] = True

    max_count = 0
    for combination in combinations(words, K - 5) :
        for a in combination :
            teach[ord(a) - ord('a')] = True

        count = solve(V, teach)
        max_count = max(max_count, count)

        # 백트래킹
        for a in combination :
            teach[ord(a) - ord('a')] = False

    print(max_count)