BOJ 1759 · 암호 만들기

알고리즘 분류 : 브루트 포스  

BOJ 6603번 '로또'와 유사한 문제다. L개의 문자 중, C개의 문자를 뽑아서 암호를 만들면 된다. 조합(Combination)을 이용한 방법으로 구현할 수 있고, 재귀 함수를 이용한 방법으로도 구현할 수도 있다.

• C++은 재귀 함수를 이용했고, Python은 조합을 이용했다.
• 모음 1개 이상, 자음 2개 이상으로 이루어진 암호인지 확인해야 한다.

---

C++ 소스코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int L, C;
char a[15];

bool possible(string passwd) {
    int vowel = 0, consonant = 0;
    for (char c : passwd) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') vowel++;
        else consonant++;
        if (vowel >= 1 && consonant >= 2) return true;
    }
    return false;
}

void solve(int index, string passwd) {
    if ((int)passwd.length() == L) {
        if (possible(passwd)) cout << passwd << '\n';
        return;
    }
    if (index >= C) return;
    solve(index+1, passwd+a[index]);
    solve(index+1, passwd);
}

int main() {
    cin >> L >> C;
    for (int i=0; i<C; i++) cin >> a[i];
    sort(a, a+C);
    solve(0, "");
    return 0;
}

---

Python 3 소스코드

from itertools import combinations
L, C = map(int, input().split())
a = sorted(input().split())
for s in combinations(a, L):
    passwd = ""
    vowel, consonant = 0, 0
    for i in range(len(s)):
        if s[i] in "aeiou":
            vowel += 1
        else:
            consonant += 1
        passwd += s[i]
        if vowel >= 1 and consonant >= 2:
            print(passwd)

---

참고

• 백준 온라인 저지 : BOJ 1759
• 로또