본문 바로가기

Programming/BOJ

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)




참고



태그