[백준/파이썬] #1062

30분 안에 풀지는 못해서 다른 풀이를 참고했다. 기존에 시도하던 방향은 백트래킹보다는 brute force에 가까웠다. 

from itertools import combinations

def solution():
    new_words = words
    answer = 0
    if K < 5:
        return answer
    
    characters_to_be_learned = []
    
    for i, word in enumerate(new_words):
        replaced_word = word
        replaced_word.replace("a", "").replace("n", "").replace("t", "").replace("i", "").replace("c", "")
        new_words[i] = replaced_word
        if replaced_word != "":
            for r in replaced_word:
                if r not in characters_to_be_learned:
                    characters_to_be_learned.append(r)

    if K == 5:
        for new_word in new_words:
            if new_word == "":
                answer += 1
        return answer
    
    max_count = 0
    count = 0
    characters_to_be_learned = "".join(characters_to_be_learned)
    for learned_words in combinations(characters_to_be_learned, K-5):
        for learned_word in learned_words:
            for new_word in new_words:
                # to be implemented
                pass
    
    return answer


if __name__ == "__main__":
    N, K = map(int, input().split())
    words = []
    for _ in range(N):
        words.append(input().strip())
    print(solution())

 

풀이를 참고해서 푼 코드는 아래와 같다. 

def solution():
    global answer
    if K < 5:
        answer = 0
        return
    elif K == 26:
        answer = N
        return

    learned = [False] * 26
    for char in ('a', 'c', 'i', 'n', 't'):
        learned[ord(char) - ord('a')] = True

    def dfs(index, count):
        global answer
        if count == K-5:
            current_learned_word_count = 0
            for word in words:
                is_word_learned = True
                for w in word:
                    if not learned[ord(w) - ord('a')]:
                        is_word_learned = False
                        break
                if is_word_learned:
                    current_learned_word_count += 1
            answer = max(answer, current_learned_word_count)
            return

        for new_index in range(index, 26):
            if not learned[new_index]:
                learned[new_index] = True
                dfs(new_index, count+1)
                learned[new_index] = False

    dfs(0, 0)


if __name__ == "__main__":
    N, K = map(int, input().split())
    answer = 0
    words = []
    for _ in range(N):
        words.append(set(input().strip()))
    
    solution()
    print(answer)