BOJ : 1759 암호 구하기

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

조건을 만족하는 부분집합을 출력하는 문제입니다. 

일반적으로 dfs로 많이 풀긴하는데 저는 비트마스크로 해결했습니다.

최소 모음 1개, 자음 2개 이상을 포함한 구문만 출력해야된다는 것만 명심하시면 될 것 같습니다.

비슷한 문제로 로또 문제가 있습니다.

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

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int L,C;
char c[16];

void code(int n){
    int place[16], consonants = 0, vowels = 0;
    int a = n, cnt = 0;
    for(int i=C-1;i>=0;i--){
        place[i] = a%2;
        if(a % 2) {
            cnt++;
            if(c[i] == 'a' || c[i] == 'e' || c[i] == 'i' || c[i] == 'o' || c[i] == 'u')
                vowels++;
            else consonants++;
        }
        a /= 2;
    }
    
    if(cnt == L && (consonants > 1 && vowels > 0)){
        for(int i=0;i<C;i++)
            if(place[i])
                printf("%c",c[i]);
    printf("\n");
    }
}
int main(){
    scanf("%d%d",&L,&C);
    for(int i=0;i<C;i++)
        scanf(" %c",&c[i]);
    sort(c, c+C);
    
    for(int i=pow(2, C); i>0; i--)
        code(i);
    
}