[백준 1759번] 암호 만들기(C++ / 완전탐색,dfs)

아이디어

일단 입력을 받은 후에 , 오름차순 정렬을 해둔다.

정렬 후 dfs(0)으로 배열의 첫부분부터 dfs를 시작해서 dfs들어갈 때마다 vector res에 push_back을 하며 진행한다.

vector에 L개 만큼의 charater가 들어오면 자음 모음의 수를 체크하고 조건에 맞다면 출력한다.

C++풀이

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int L,C;
vector<char> v; 
vector<char> res;

bool check()
{
    int moum = 0;
    for(int i = 0 ; i< L ; i++)
    {
        if(res[i] == 'a' ||
           res[i] == 'e' ||
           res[i] == 'i' ||
           res[i] == 'o' ||
           res[i] == 'u')
           moum++;
    }
    // 모음의 수 1개 이상, 자음의수 = 전체수 -모음의 수 . 2개이상.
    if(moum >=1 && L-moum >=2) return true; 
    return false;
}
void dfs(int d){
    if((int)res.size()==L){
        if(check()){ //check에서 조건 부합시 출력.
            for(int k = 0 ; k< L ; k++)
            {
                cout << res[k];
            }
            cout << '\n';
        }
        return;
    }
    for(int i = d ; i< C; i++)
    {
        res.push_back(v[i]); //들어갈때 하나씩 추가해주고
        dfs(i+1);
        res.pop_back(); //나오면 하나 빼주고.
    }
    return;
}
int main(void)
{
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> L  >> C;
    for(int i = 0 ; i< C ; i++)
    {
        char temp;
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end()); //정렬하고 dfs(0)시작.
    dfs(0);
}