[BOJ] 1759 - 암호만들기

김우경·2021년 5월 2일
0

알고리즘

목록 보기
60/69

문제 링크

1759 - 암호만들기

문제 설명

암호는 서로 다른 L개의 알파벳 소문자로 구성되고, 최소 한개의 모음과 최소 두개의 자음으로 구성된다. 또한, 암호는 알파벳이 증가하는 순서로 배열된다.

사용했을 법한 문자의 종류가 C가지가 있을때, 가능성있는 암호들을 모두 구하시오.

문제 풀이

combinations를 사용해서 간단하게 풀 수 있는 문제다.

C개의 문자 중에서 가능한 모든 L개의 조합을 구하고, 그 중에서 1개 이상의 모음, 2개 이상의 자음을 갖는 암호를 찾는다.

import sys
from itertools import combinations

input = sys.stdin.readline

L, C = input().split()
chars = sorted(list(input().split()))

vowels = ['a', 'e', 'i', 'o', 'u']
combination = combinations(chars, int(L))
answer = []

for com in combination:
    n_v, n_c = 0, 0
    for c in com:
        if c in vowels:
            n_v += 1
        else:
            n_c += 1
    if n_v >= 1 and n_c >= 2:
        answer.append(com)
        
answer.sort()
for a in answer:
    print(''.join(a))

분류는 백트래킹이던데 백트레킹으로도 풀어봐야쥐

profile
Hongik CE

0개의 댓글