[BaekJoon] 1759 암호 만들기 :: monton

문제

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

풀이

모든 경우의 수를 체크 해야 하므로 dfs 사용

arr 배열에 주어진 알파벳을 담고 visit 배열을 사용해 어떤 인덱스를 방문 했는지 체크하였다

알파벳 모음은 a,e,o,i,u로 총 5개 이며 모음이 최소 1개, 자음이 최소 2개라는 조건을 맞추기 위해 둘다 카운트한다

모두 C번을 방문하였다면 모음이 최소 1개, 자음이 최소 2개라는 조건을 맞추었는지 확인하고 그렇지 않다면 반환한다

만약 맞다면 visit 배열 중 1인 인덱스만 arr를 차례대로 출력해 준다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int L, C;
char arr[16];
int visit[16];
 
void func(int x, int cnt,int n, int m) { //n은 모음,m은 자음
    if (cnt == L) {
        if (n < 1 || m < 2) return;
        for (int i = 0; i < C; i++) {
            if (visit[i]) cout << arr[i];
        }
        puts("");
        return;
    }
 
    for (int i = x; i < C; i++) {
        if (!visit[i]) {
            visit[i] = 1;
            int nn=n, nm=m;
            
            if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'u' || arr[i] == 'o') nn += 1;
            else nm += 1;
 
            func(i, cnt + 1, nn, nm);
            visit[i] = 0;
        }
    }
}
 
int main() {
    cin >> L >> C;
 
    for (int i = 0; i < C; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + C);
    func(0, 0, 0, 0);
 
}