[백준 BOJ_1062] 가르침 Python 풀이

출처: 백준 온라인 저지

문제

풀이

backtracking으로 풀었습니다.

우선 배운 알파벳을 체크해주기 위해 learned 라는 list를 만들어줍니다. 모든 단어는 기본적으로 “anta”로 시작하고 “tica”로 끝나야 하기때문에 “a”, “c”, “i”, “n”, “t”는 꼭 배워야합니다. 그러므로 이전에 learned에 배웠다고 표시해둡니다.

그리고 입력받는 모든 단어들을 “anta”, “tica”를 제외시킨 단어로 저장해줍니다.

이후에는 k_cnt가 K가 될 때까지 모든 경우의 수를 돌아주며 배울 수 있는 최대 단어의 수를 세어줍니다.

K가 5보다 작다면 “anta”, “tica”도 포함할 수 없기 때문에 5보다 작을 경우는 아무 단어도 배울 수 없습니다. 그러므로 그 경우에는 0을 출력해줍니다.

코드

N, K = map(int, input().split())
words = []
result = 0
learned = [0 for _ in range(26)]

for ch in "acint":
    learned[ord(ch)-ord("a")] = 1

def backtrack(idx, k_cnt):
    global words, result, K
    if k_cnt == K:
        cnt = 0
        for word in words:
            for w in word:
                if not learned[ord(w)-ord("a")]:
                    break
            else: cnt += 1
        result = max(result, cnt)
        return

    for i in range(idx, 26):
        if not learned[i]:
            learned[i] = 1
            backtrack(i, k_cnt+1)
            learned[i] = 0

for _ in range(N):
    input_word = input()
    words.append(set(input_word[4:-4]))

if K >= 5:
    backtrack(0, 5)
    print(result)
else: print(0)