백준 #1759 암호 만들기

백준 #1759 암호 만들기

알파벳 C 개 중 L 개를 고르는 조합을 모두 출력하는 문제. 단, 적어도 모음 한 개와 자음 두 개가 있어야 한다.
재귀적으로 조합을 구하는 알고리즘을 사용하면 구할 수 있다.

알파벳 C개를 모두 정렬 후, 첫 알파벳부터 고르거나 고르지 않거나를 selected라는 string에 저장하여 인자로써 재귀적으로 넘겨준다. 이 때 모음과 자음의 개수 또한 계산해 인자로 넘겨준다. 총 L개를 골랐을 때, 모음이 적어도 한 개, 자음이 적어도 두 개일 경우 selected를 출력한다.

#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <algorithm>

using namespace std;

int L, C;



void comb(string& alphList, string selected, int idx, int vCount, int cCount) {
    if(selected.size() == L && vCount >= 1 && cCount >= 2) {  // selected의 size가 L인 경우(다 고름)
        cout << selected << "\n";
        return;
    }
    if(idx >= C) {   //index가 전체 알파벳 개수를 넘길 때(다 못 고르는 경우)
        return;
    }
    selected.push_back(alphList[idx]); //고르는 경우
    if(alphList[idx] == 'a' || alphList[idx] == 'e' || alphList[idx] == 'i' || alphList[idx] == 'o' || alphList[idx] == 'u') { //모음일 경우 vCount + 1
        comb(alphList, selected, idx + 1, vCount + 1, cCount);
    }
    else {
        comb(alphList, selected, idx + 1, vCount, cCount + 1); //자음일 경우 cCount + 1
    }
    selected.pop_back();
    comb(alphList, selected, idx + 1, vCount, cCount); //고르지 않는 경우
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> L >> C;
    string alphList = "";
    string selected = "";
    for(int i = 0; i < C; i++) {
        char c;
        cin >> c;
        alphList.push_back(c);
    }
    sort(alphList.begin(), alphList.end());
    comb(alphList, selected, 0, 0, 0);
    return 0;
}