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

문제

https://www.acmicpc.net/problem/1759

백준 1759

 

문제 내용

입력받은 알파벳 C개로 암호(길이 L)를 구성하면 된다. (주어지는 입력은 모두 소문자이며 중복은 없다.)

이때 만든 암호는, 알파벳이 증가하는 순서여야 하며, 모음이 최소 1개, 자음도 최소 2개를 포함해야 한다. (중복 X)

위 조건에 맞는 암호를 사전식으로 출력하면 된다.

 

문제 풀이

백트래킹으로 문제를 해결하면 된다. 

기본적인 백트래킹 코드를 통해, 중복 없고 알파벳이 증가하는 순서로 암호를 만드는 것이 가능하다.

단, 모음 1개 이상, 자음 2개 이상 포함했는지는 출력 직전에 검사하도록 했다.

 

코드

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

int L, C;

char arr[15];
vector<char> result;

bool checkVowel(char ch) {
    switch (ch) {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
        return true;
    default:
        return false;
    }
}

bool checkValidation() {
    int vowel = 0, consonant = 0;
    for (auto ch : result) {
        if (checkVowel(ch)) {
            vowel++;
        } else {
            consonant++;
        }
    }

    return (vowel >= 1 && consonant >= 2);
}

void secretCode(int num, int idx) {
    if (num == L) {
        if (!checkValidation()) // 자음모음 개수 체크
            return;

        // 출력
        for (auto ch : result)
            cout << ch;
        cout << "\n";
        return;
    }

    for (int i = idx + 1; i < C; i++) {
        result[num] = arr[i];
        secretCode(num + 1, i);
    }
}

int main() {
    cin >> L >> C;
    for (int i = 0; i < C; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + C);
    result.assign(L, ' ');
    secretCode(0, -1);
}