백준 1062 가르침 Python

🐸 문제 정보

1062번: 가르침

 

🤖 알고리즘

백트래킹

 

⏱️ 풀이 시간

60m+

 

📝 풀이

예전에 한 번 풀었던 문제인데도 기억을 못해서 오래걸렸다..

알파벳 26개에 대해, 가르쳤는지 여부를 알 수 있는 26개의 요소 리스트를 선언한다.

각 알파벳에 대해서 True(가르침)을 넣어보고 학생이 총 알 수 있는 단어의 개수를 파악한 뒤, 해당 알파벳을 False(가르치지 않음)으로 바꿔보면서 백트래킹을 실시한다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
letters = [False] * 26
words = [list(input().rstrip()) for _ in range(n)]

for letter in ['a', 'n', 't', 'i', 'c']:
    letters[ord(letter) - ord('a')] = True

if k < 5:
    print(0)
    exit()

if k >= 26:
    print(n)
    exit()

res = 0

def bt(prev, cnt):
    global res
    if cnt == k - 5:
        temp = 0
        for word in words:
            flag = False
            for letter in word:
                if not letters[ord(letter) - ord('a')]:
                    flag = True
                    break
            if not flag: temp += 1
        res = max(res, temp)
        return
    for i in range(prev, 26):
        if not letters[i]:
            letters[i] = True
            bt(i, cnt + 1)
            letters[i] = False

res = 0
bt(0, 0)
print(res)