[백준/파이썬] 1062번 가르침

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

1062번: 가르침

백트래킹을 이용한 브루트 포싱이다.

 

단어의 앞뒤가 항상 anti, tica로 이루어져 있으므로 최소 5개의 글자 (a,c,i,n,t) 는 알고 있어야 한다.

그리고 이제 남은 알파벳 21개 중에서 추가로 학습을 진행한다. 이 때 알고 있는 글자의 수가 k개가 될 때 까지만 진행한다.

 

만약 depth가 k에 도달한다면, 입력으로 주어진 단어를 탐색하면서 모르는 글자가 나올 경우 탐색을 종료하면 된다.

내가 아는 글자로만 이루어진 단어를 만났을 때만 counting 해주면 된다!

import sys
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, k= map(int, input().split())
alpha = [False for _ in range(26)]
words = [input().rstrip() for _ in range(n)]
ans =0

def check():
  cnt = 0
  for word in words:
    flag = True
    for s in word:
      if not alpha[ord(s)-97]:
        flag = False
        break
    if flag:
      cnt += 1
  return cnt

def dfs(start, depth):
  global ans
  
  if depth == k:
    ans = max(ans, check())
    return

  for i in range(start, 26):
    if not alpha[i]:
      alpha[i] = True
      dfs(i, depth+1)
      alpha[i] = False
      
# 메인 함수
def main():
  if k < 5:
    print(0)
  elif k == 26:
    print(n)
  else:
    for c in ('a', 'c', 'i', 'n', 't'):
        alpha[ord(c) - ord('a')] = True

    dfs(0, 5)

    print(ans)

if __name__ == '__main__':
    main()