백준 1062 가르침

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

오랜만에 포스팅...

문제를 보면 처음에는 기본으로 배워야 하는 단어 a,n,t,i,c를 뺀 나머지 알파벳 중에서 k-5개의 조합을 구해서 일일이 다 문자열마다 비교해봤다.
파이썬 set를 이용해서 모든 경우의 수를 다 구해보니 시간초과가 나왔다.

그렇기 때문에 가지치기를 해야하는데, k-5개의 모든 조합을 구해보는 것이 아닌 백트래킹을 통해 경우의 수를 줄일 수 있었다.

k가 5보다 작은 경우 조합을 할 수 없고, k가 26이라면 모든 글자를 다 가르칠 수 있기 때문에 n을 출력하면 된다.

기본으로 배워야 하는 단어 5가지를 먼저 백트래킹을 위한 배열에 1로 채워주고, 나머지 알파벳에 대해서 k-5가지 만큼 백트래킹 하면 된다.

백트래킹 분기의 마지막이라면, 단어의 알파벳이 백트래킹 배열에 모두 채워져 있는지 확인하고, for-else문을 이용해 for문의 흐름 중간에서 break가 된다면 배운 단어의 개수를 하나 증가시켰다.

n,k = list(map(int,input().split()))
words = []
ans = 0
for i in range(n):
    words.append(input())

if k < 5:
    print(0)
    exit(0)
if k == 26:
    print(n)
    exit(0)

study = [0] * 26
for alphabet in ['a','n','t','i','c']:
    study[ord(alphabet) - ord('a')] = 1

def dfs(idx, cnt):
    global ans
    if cnt == k - 5:
        word_count = 0
        for word in words:
            for alphabet in word:
                if not study[ord(alphabet) - ord('a')]:
                    break;
            else:
                word_count += 1

        ans = max(ans,word_count)
        return

    for i in range(idx,26):
        if not study[i]:
            study[i] = 1
            dfs(i,cnt+1)
            study[i] = 0

dfs(0,0)

print(ans)