백준 1759 암호 만들기

브루트포스 알고리즘을 사용하는 문제를 찾아서 풀어보았다.

순서대로 조건에 맞는 문자열의 모든 경우의 수를 출력하면 된다.

다른 코테에서 풀어본 적 있는 문제라 유사하게 풀어봤다.

 

사용 가능한 문자들을 입력받은 뒤, 알파벳 순으로 정렬한다.

그 배열을 사용해 DFS로 한 글자씩 붙여가며 탐색을 한다.

길이를 확인해 우리가 원하는 길이가 되면, 조건을 확인한다. 여기서 조건은 모음과 자음의 개수이다.

조건이 맞으면 출력한다. 알파벳순으로 문자들을 정렬했기에 조건에 맞을때마다 출력하면 된다.

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int l, c;
std::vector<char> alpha;

bool checkVowel(std::string cur)
{
    int Vowel = 0;
    int Conson = 0;
    for (char c : cur)
    {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
            Vowel++;
        else
            Conson++;
    }
    if (Vowel >= 1 && Conson >= 2)
        return true;
    else
        return false;
}

void dfs(int len, std::string cur)
{
    if (len == l)
    {
        if (len > 2 && checkVowel(cur))
            std::cout << cur << '\n';
        return;
    }
    else
    {
        for (char c: alpha)
        {
            if (cur[cur.size()-1] < c)
                dfs(len+1, cur+c);
        }
    }
}

int main()
{
    std::cin >> l >> c;
    for (int i = 0; i < c; i++)
    {
        char tmp;
        std::cin >> tmp;
        alpha.push_back(tmp);
    }
    std::sort(alpha.begin(), alpha.end());
    dfs(0, "");
}

 

좀 간단하다. 다른 문제들도 풀어봐야겠다. 한번에 풀고 거의 바로 솔루션 되어서 좋았다 후후후후

오늘도 평온한 하루가 되길. 슨민.