[백준] 1759 암호만들기

약간의 백트래킹 방법에서 살짝만 바뀐 방법으로 문제를 해결할 수 있다.

 

일반적으로라면 count를 증가시켜 확인 후 return; 하지만

해당 문제는 모음 개수와 자음 개수를 따로 계산하여 가져가야한다.

 

나머지는 백트래킹 하듯이 하면 해결할 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

int L1759, C1759;
vector<char> input1759;
vector<char> result1759;
vector<bool> check1759(16,false);
char vowelList1759[] = {'a','e','i','o','u'};

void backback1759(int pos, int vowelCount, int conCount){
    
    if(vowelCount + conCount == L1759 and vowelCount >= 1 and conCount >= 2){
        for(int i=0;i<L1759;++i)
            cout<<result1759[i];
        cout<<"\n";
        return;
    }
    
    
    for(int i=pos; i<C1759; ++i){
        if(!check1759[i]){
            bool check = true;
            check1759[i] = true;
            result1759.push_back(input1759[i]);
            
            for(int j=0;j<5;++j)
                if(input1759[i] == vowelList1759[j])
                    check = false;
            
            if(check)
                backback1759(i+1, vowelCount, conCount+1);
            else
                backback1759(i+1, vowelCount+1, conCount);
                
            result1759.pop_back();
            check1759[i] = false;
        }
    }
    
}

void password1759(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>L1759>>C1759;
    
    
    for(int i=0; i<C1759; ++i){
        char a; cin >> a;
        input1759.push_back(a);
    }
    
    sort(input1759.begin(), input1759.end());
    
    backback1759(0, 0, 0);
}