[Boj] 암호 만들기 1759(python)

문제링크 : https://www.acmicpc.net/problem/1759

암호 길이 L과 암호를 만들 수 있는 문자의 갯수 C가 주어지고, 다음 줄에서는 암호를 만들 수 있는 문자가 입력됨

처음에는 itertools.premuations을 사용했으나, 메모리 초과로 DFS로 선회함

DFS를 사용하되, 암호에 마지막 글자가 추가되는 글자보다 사전순으로 앞선지를 보기 위해 ord(x) 사용

한편, 종료조건은 처음에는 만든 암호의 길이가 L가 같다는 것으로 했으나,

문제를 읽어보니 최소 자음 2개와 모음 1개는 반드시 있어야만 했음

이를 다 풀고나서 20분 후에 발견하여, 이를 추가해줌

결론 : 문제조건을 잘 읽자….

import sys
sys.setrecursionlimit(10**8)
from itertools import permutations

def DFS(answer):

    if len(answer) == L:
        vowel_cnt = 0
        not_vowel_cnt = 0
        for word in answer:
            if word in vowels:
                vowel_cnt += 1
            else:
                not_vowel_cnt += 1
        if vowel_cnt >= 1 and not_vowel_cnt >= 2:
            print(answer)
        return
    if len(answer) < L:
        for tmp in words:
            if ord(answer[-1]) < ord(tmp):
               DFS(answer+tmp)
    return

L, C = map(int, input().split())

words = list(map(str, input().split()))
vowels = ['a', 'e', 'i', 'o', 'u']
words.sort()

for start in words:
    DFS(start)