[C++] Boj 1759 암호 만들기

문제 링크

1759 암호 만들기

---

접근

조건을 만족하는 모든 경우의 수를 찾는 문제이므로 백트래킹을 사용하여 풀이하였다.

 

---

알고리즘

k번째 문자를 뽑기 위해 다음과 같은 절차를 거친다.

 

만약 지금 뽑을 문자가 이미 사용되었다면, continue

만약 지금 뽑을 문자가 이전에 뽑은 문자보다 사전순으로 앞에 있다면, continue (증가하는 순서로 배열되어야 하기 때문)

 

문자를 뽑는다.

 

만약 이 문자가 모음이라면, 모음 개수를 +

만약 이 문자가 자음이라면, 자음 개수를 +

 

여기까지 왔다면, 문자가 사용된 것도 아니고, 사전순에 위반하는 문자도 아니므로 문자를 확정해 준다.

이후 사용했다고 중복 배열에 표시.

 

다음, k + 1 번째 문자를 뽑기 위해 재귀함수를 실행한다.

 

이렇게 진행하다가 필요한 모든 문자를 다 뽑았다면, 마지막으로 최소 조건인 자음 개수 2, 모음 개수 1을 맞췄는지 확인한다.

이후 출력한다.

 

---

 

코드

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

// 암호는 최소 한 개의 모음, 최소 두 개의 자음으로 구성되어야 함

int L; // 암호의 총 길이
int C; // 주어진 문자의 개수

// 모음
int vowels[5] = { 'a', 'e', 'i', 'o', 'u' };

// 암호로 뽑은 문자열
char picked[16];

// 현재 사용 가능한 문자들
char chars[16];

// 중복 사용 확인 배열
bool isUsed[16];

// 모음, 자음 개수가 조건을 만족하는지 확인
int isVowle;
int isConsonant;

// k 번째로 지정할 문자를 탐색 
void Solve(int k)
{
    if (k == L)
    {
        // 모음, 자음 개수가 조건을 충족한다면
        if (isVowle >= 1 && isConsonant >= 2)
        {
            for (int i = 0; i < L; i++)
            {
                cout << (char)picked[i];
            }
            cout << '\n';
        }
        return;
    }

    for (int i = 0; i < C; i++)
    {
        if (isUsed[i] || (k > 0 && picked[k - 1] > chars[i])) continue;

        // 만약 현재 문자가 모음이면
        if (find(vowels, vowels + 5, chars[i]) != std::end(vowels))
        {
            isVowle++;
        }
        // 만약 현재 문자가 자음이면
        else
        {
            isConsonant++;
        }

        isUsed[i] = true;
        picked[k] = chars[i];
        Solve(k + 1);
        isUsed[i] = false;

        // 만약 현재 문자가 모음이면
        if (find(vowels, vowels + 5, chars[i]) != std::end(vowels))
        {
            isVowle--;
        }
        // 만약 현재 문자가 자음이면
        else
        {
            isConsonant--;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> L >> C;

    for (int i = 0; i < C; i++)
    {
        cin >> chars[i];
    }

    sort(chars, chars + C);

    Solve(0);

    return 0;
}