10. 암호 만들기
- 서로 다른 L개 알파벳, 문자의 종류는 C
- 최소 1개의 모음과 최소 2개 자음으로 구성되어 있을 때,
- 예제를 본다면, 6개 중 4개를 뽑는데 그 때 모음은 최소 1개, 자음은 최소 2개가 있어야 한다.
백트래킹을 이용하여 문제를 푼다. 최소 한 개의 모음과 최소 두 개의 자음으로 구성 -> 최종 결과를 통해 확인하기 암호는 알파벳이 증가하는 순서로 배열 -> 처음에 오름차순으로 정렬해서 백트래킹하면 해결
def check(arr): # 조건 체크해주는 함수
aeiou, remainder = 0, 0
for i in arr:
if i in "aeiou":
aeiou += 1
else:
remainder += 1
if aeiou >= 1 and remainder >= 2:
return True
def DFS(s):
global result
if len(result) == L:
if check(result):
print("".join(map(str, result)))
return
for i in range(s, C):
if not visited[i]:
visited[i] = True
result.append(arr[i])
DFS(i)
result.remove(arr[i])
visited[i] = False
L, C = map(int, input().split())
arr = sorted(list(input().split()))
visited = [False]*(C+1)
result = []
DFS(0)
참고자료