1062 가르침

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

#완전 탐색

#백트래킹

1062번: 가르침

 

#1062 가르침 정리

 

from sys import stdin

#stdin 수입

#시간초과를 없애야 한다.

 

input=stdin.readline

#input 변환

 

def solution(index,count):

global max_answer

#max_answer 전역함수로 변경

 

if count==0:

#함수를 끝낼 조건

 

answer=0

for i in set_word_list:

for j in i:

if not alpha[ord(j)-ord('a')]:
break

else:

answer+=1

max_answer=max(answer,max_answer)

#단어 리스트를 집합으로 해놓은 것을 열어서 각 알파벳이 alpha 인덱스('a'는 0이라는 가정)에서 트루인지 확인후 아니면 바로 캔슬 다 통과되면 answer +=1 그리고 max_answer를 갱신합니다

 

else:

for i in range(index,26):
if not alpha[i]:

alpha[i]=True

solution(i+1,count-1)

alpha[i]=False

#백트래킹의 조건 26까지 인덱스를 하나씩 올리면서 true false 움직인다.

 

n,k=map(int,input().split())

#n,k입력

word_list=[input().rstrip() for i in range(n)]

#stdin 이므로 rstrip 을 이용해서 \n이 입력 되지않게 막아주어야 합니다.

set_word_list=[]

#집합을 이용할 단어 리스트

alpha_set=set([])

#필요한 알파벳을 담을 집합

for i in word_list:

alpha_set|=set(i)

#필요한 알파벳의 집합과 list에 있는 알파벳들을 집합화시켜 합집합 

set_word_list.append(set(i))

#집합을 이용할 단어 리스트 저장

alpha=[False for i in range(26)]

#dp 비슷하게 아스키코드를 이용할 알파벳 리스트 작성

max_answer=0

for i in ['a','n','t','i','c']:

alpha[ord(i)-ord('a')]=True

#antic는 이미 배웠다고 가정하고 true

if k<5 or k>=len(alpha_set):

print(0 if k<5 else n)

#필요한 알파벳보다 배울 알파벳의 수가 더 크면 무조건 단어의 개수 출력 

else:

solution(0,k-5)

#인덱스 0 부터 k에 antic를 뺸 수를 이용해서 함수를 돌린다.

print(max_answer)

#답 만들기

 

#개힘들다 죽고싶다 하지만 의미있었다. 완전탐색을 제대로 알 수있었으며 백트래킹을 활용하여 모든 경우의 수를 다 살펴보는 그런 시간이였다.