[백준][C++] 1759: 암호 만들기

문제

1759번: 암호 만들기

풀이

수학, 브루트포스 알고리즘, 조합론, 백트래킹

 

사전순으로 출력되어야 하므로 미리 입력받은 문자를 정렬시킨 후에 시작한다. 문자열의 길이는 최대 15로 모든 경우의 수를 탐색해도 시간 초과가 발생하지 않는다. 

 

정렬된 문자열의 앞의 문자부터 선택과 선택해제를 반복하며, 선택된 문자열의 길이가 L이라면 정답 조건을 만족하는지 확인한다. 백트래킹으로 문자를 선택한다.

void dfs(int index)
{
    // 선택한 문자의 수가 L에 충족한다면 조건에 맞는지 검사
    if (answer.size() == L)
    {
        if (check())
        {
            for (int i = 0; i < answer.size(); ++i)
            {
                cout << answer[i];
            }
            cout << '\n';
        }

        return;
    }

    // 백트래킹으로 문자를 선택
    for (int i = index; i < C; ++i)
    {
        answer.push_back(chars[i]);
        dfs(i + 1);
        answer.pop_back();
    }

}

 

 

코드

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

using namespace std;

int L, C;
vector<char> chars;
vector<char> answer;

bool check()
{
    // 모음이 1개 이상이며 자음이 2개이상
    int vowel = 0;
    
    for (int i = 0; i < answer.size(); ++i)
    {
        if (answer[i] == 'a' || answer[i] == 'e' || answer[i] == 'i' || answer[i] == 'o' || answer[i] == 'u')
        {
            vowel++;
        }
    }

    return (vowel >= 1) && (L - vowel >= 2);
}

void dfs(int index)
{
    // 선택한 문자의 수가 L에 충족한다면 조건에 맞는지 검사
    if (answer.size() == L)
    {
        if (check())
        {
            for (int i = 0; i < answer.size(); ++i)
            {
                cout << answer[i];
            }
            cout << '\n';
        }

        return;
    }

    // 백트래킹으로 문자를 선택
    for (int i = index; i < C; ++i)
    {
        answer.push_back(chars[i]);
        dfs(i + 1);
        answer.pop_back();
    }

}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> L >> C;

    for (int i = 0; i < C; ++i)
    {
        char temp;
        cin >> temp;

        chars.push_back(temp);
    }

    // 미리 정렬
    sort(chars.begin(), chars.end());

    dfs(0);

    return 0;
}