(C++) - 백준(BOJ) 1759번 : 암호 만들기

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

1759번: 암호 만들기

 

재귀를 통해 적절히 모든 경우의 수를 탐색하면 됩니다.

 

풀이방법

 1. 사전순으로 c개의 알파벳을 l개만큼 순서에 상관 없이 뽑아줍니다.

 2. 모음이 최소 1개, 자음이 최소 2개라면 정답이므로 출력해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int l,c,ck[16];
char letter[16];
vector <char> candidates;
void dfs(int depth, int idx){
    if(depth == l) {
        int vowel = 0,consonant = 0;
        for(auto can : candidates){
            if(can == 'a' || can == 'e' || can == 'i' || can == 'o' || can == 'u') vowel++;
            else consonant++;
        }
        if(vowel < 1 || consonant < 2) return ;
        for(auto c : candidates) cout << c;
        cout << '\n';
        return;
    }
    for(int i = idx; i < c; i++){
        if(ck[i]) continue;
        ck[i] = 1;
        candidates.push_back(letter[i]);
        dfs(depth + 1, i + 1);
        candidates.pop_back();
        ck[i] = 0;
    }
}

int main(){
    cin >> l >> c;
    for(int i = 0; i < c; i++){
        cin >> letter[i];
    }
    sort(letter,letter + c);
    dfs(0,0);
}