[백준] 1759번 암호만들기

 

[적용한 알고리즘]

백트래킹, 재귀

 

[아이디어]

포함이 되는가 안되는가를 이용해서 재귀함수를 짜주면 될 것 같았다.

경우의 수도 2^15 개라 32768 충분하다.

 

모음 1개 이상 자음 2개 이상도 체크해줘야 하므로,

인덱스가 배열의 끝을 가르키고 있을 때 원하는 결과에 맞는다면 출력해주게끔 하면 될 것이다.

 

[생각의 흐름 / 절차] 

1. len, n 을 입력 받고 입력 받은 알파벳들을 사전 순으로 정렬을 해준다.

2. 재귀함수에 넘겨줄 인자들은 현재 배열의 인덱스 값, 모음의 개수, 자음의 개수다. 

3. 탈출 조건을 설계 해야한다.

만약 인덱스가 배열의 끝이라면 모음 + 자음이 암호의 길이와 일치하는지 검사, 

그리고 모음과 자음의 개수가 문제의 조건에 맞는지를 살핀다. 

맞으면 걔네들 출력 후 리턴

4. 먼저 선택하는 경우를 고려해준다.

ans에 넣어주려는 애가 자음인지 모음인지 알아야함.

그래서 검사해주고, 상황에 맞게 재귀 호출을 해주면 됨.

5. 넣어주는 경우의 재귀가 끝나면 넣어줬던 문자를 다시 pop 해줘야 다음 암호로 넘어간다.

6. 선택 안하는 경우를 고려해준다. 인덱스+1 만 넘겨주는 거.

 

[교훈]

넣는 경우에서 넣었다가 빼주는 게 정확히 와닿지는 않았는데, 그림 그려보니 너무 당연했음.

 

<코드>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int len, n;
char arr[16];
char m[] = {'a', 'e', 'i', 'o', 'u'};
vector<char> ans;

void go(int idx, int mo, int ja){
    if (idx == n){
        if (mo + ja == len && mo >= 1 && ja >= 2){
            for (int i = 0; i < len; i++){
                printf("%c", ans[i]);
            }
            printf("\n");
        }
        return;
    }

    //선택하는 경우
    ans.push_back(arr[idx]);
    bool isMo = false;
    for (int i = 0; i < 5; i++){
        if (arr[idx] == m[i]){
            go(idx + 1, mo + 1, ja);
            isMo = true;
            break;
        }
    }
    if (!isMo){
        go(idx + 1, mo, ja + 1);
    }
    ans.pop_back();

    //선택안하는 경우
    go(idx + 1, mo, ja);
}

int main(){
    scanf("%d %d", &len, &n);
    for (int i = 0; i < n; i++){
        scanf(" %c", &arr[i]);
    }

    sort(arr, arr + n);

    go(0, 0, 0);
    return 0;
}