[백준] 1062번 : 가르침

1062번: 가르침

해당 문제는 조합 문제로 해결 하였습니다. 알파벳의 모든 경우의 수를 구한뒤에, 알파벳으로 읽을 수 있는 단어를 계산합니다.

알파벳을 읽을 수 있는 learned 배열을 통하여 읽을 수 있는 알파벳을 표기하고 단어중에 learned 값이 모두 있다면 카운트를 증가시킵니다.

from itertools import combinations

N, K = map(int, input().split())
northword = list(['a','n','t','i','c'])
alpabat = list(['b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z'])

words = list()

for _ in range(N):
    word = list(input())
    words.append(word)
    

learned = [False for _ in range(26)]

for alpa in northword:
    learned[ord(alpa)-ord('a')] = True

maxcounter = 0

if K-4 > 0:
    for alpalist in combinations(alpabat, K-5):
        count = 0
        
        for alpa in alpalist:
            learned[ord(alpa)-ord('a')] = True
            
        # 계산하는 로직과 max값 리뉴얼
        for word in words:
            canRead = True
            for temp in word:
                if not learned[ord(temp)-ord('a')]: # 배우지 않는 알파벳이 있다면
                    canRead = False
                    break
            
            if canRead:
                count += 1
                    
        if count > maxcounter:
            maxcounter = count
            
        for alpa in alpalist:
            learned[ord(alpa)-ord('a')] = False
            
    print(maxcounter)
else:
    print(0)