[백준] 1759번(python 파이썬)

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

 

조합관련 문제이다. itertools의 combinations을 사용해도 되지만 백트래킹으로 풀었다.

 

사실 간단한 문제인데 문제를 제대로 읽지 않았다..

 

처음에 대충 읽고 푼게 모음만 하나 이상이면 된다고 생각하여 풀었는데 오답이 나와서 다시 문제를 보니 자음도 최소 2개 이상 나와야 한다고 적혀있었다.

첫번째 잘못 이해..

 

그리고 왠지 모르겠지만 모음이 연속으로 나오면 안된다고 적혀있지도 않는데 연속으로 나오지 않도록 풀었다...

두번째 잘못 이해..

 

문제를 꼼꼼히 보자..

l, c = map(int, input().split())
cipher = list(input().split())
visited = [False] * c
vowels = ['a', 'e', 'i', 'o', 'u']
cipher.sort()

string =""

def BackTrack(depth, start):
    global string
    if depth == l:
        Vaildation(string)
        return

    for i in range(start, c):
        if visited[i]:
            continue
        visited[i] = True
        string += cipher[i]
        BackTrack(depth+1, i)
        string = string[:-1]
        visited[i] = False

def Vaildation(string):
    vowel_count = 0
    consonant_count = 0
    for i in range(len(string)):
        if string[i] in vowels:
            vowel_count += 1
        else:
            consonant_count += 1

        if i == len(string) - 1:
            if vowel_count >= 1 and consonant_count >= 2 :
                print(string)

BackTrack(0, 0)