[백준][python]1062 가르침

문제

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

소스코드

import sys
input = sys.stdin.readline
if __name__ == "__main__":
    n,k = map(int,input().split())
    
    if k < 5:
        print(0)
        exit()
    elif k == 26:
        print(n)
        exit()

    answer = 0
    chk = [set(input().rstrip()) for _ in range(n)]
    alpha = [0] * 26
    for a in ['a','n','t','i','c']:
        alpha[ord(a)-ord('a')] = 1

    def dfs(l,idx):
        global answer
        if l == (k-5):
            cnt = 0
            for chk_str in chk:
                tmp_chk = True
                for c in chk_str:
                    if not alpha[ord(c)-ord('a')]:
                        tmp_chk = False
                        break
                if tmp_chk:
                    cnt+=1
            answer = max(answer,cnt)
            return
        for i in range(idx,len(alpha)):
            if not alpha[i]:
                alpha[i] = 1
                dfs(l+1,i)
                alpha[i] = 0
    dfs(0,0)
    print(answer)

설명

고정 알파벳이 있으므로 k가 5개보다 적으면 아무 문장도 못읽음

알파벳 26개를 다 안다면 모든 문장을 다 읽을 수 있음 (처음에 이거 안해줬는데 안하면 시간 초과 발생함)

 

'a', 'n', 't', 'i', 'c' 는 무조건 고정이다. 알파벳 체크 배열을 만들어서 해당 문자는 1로 초기화 해준다.

알파벳을 체크하는 배열은 문자 그대로 하기 보단 아스키코드로 치환해서 배열을 초기화해준다

 

DFS를 이용해서 K 만큼의 알파벳을 배웠다면 (알파벳 체크 함수가 K개가 1로 체크 됬다면) 문장안에 알파벳을 읽을 수 있는지 없는지 체크해준다.

 

DFS에서 알파벳 체크 함수를 기준으로 백트래킹을 해주면서 배웠다 안배웠다를 체크한다.

이때 반드시 그전까지 체크한 인덱스를 함께 파라미터로 보내서 그 이후부터 체크해줘야한다.(이걸 안해줘서 처음에 시간초과 발생)