백준 1759 암호 만들기

최소 한 개의 모음과 두 개의 자음을 이용하여 l 만큼의 길이로 단어를 뽑으면 되는 문제이다. 또한 단어를 사전 순으로 출력하면 된다.

주어진 단어 리스트 중에서 l 개를 뽑으면 되는 문제로 변환할 수 있다.

즉, 백트래킹을 이용한다면 문제를 쉽게 풀 수 있다.

def recursive(idx, path):
    if len(path) == l:
        cnt = 0     # 모음이 한 개인지 확인하는 변수
        cnt2 = 0	# 자음 확인 변수
        for i in range(len(path)):
            if path[i] in ['a', 'e', 'i', 'o', 'u']:
                cnt += 1
            else:
                cnt2 += 1
        if cnt >= 1 and cnt2 >= 2:
            print(*path,sep='')
        return

    for i in range(idx, len(lis)):
        if lis[i] not in path:
            path.append(lis[i])
            recursive(i, path)
            path.pop()



l, c = map(int, input().split(" "))
lis = list(map(str, input().split(" ")))
lis.sort()

recursive(0, [])