#1759 암호 만들기

문제 정리

C: 알파벳 전체 후보
C 중 L개만 사용해서 암호 만드는데
최소 1개의 모음, 최소 2개의 자음 포함.
오름차순 정렬
가능성 있는 암호 전부 출력

생각해보기

백트래킹…

받은 C 전체 오름차순 정렬부터.
첫 자리가 모음이면 모음 + 1, 자음이면 자음 +1 하고 그 문자 저장하고 다음 문자 탐색
다음 문자 탐색할 땐 위에서 찾은 문자의 인덱스 + 1부터 찾음
똑같이 계속 재귀 써서 하다가 글자수가 L이고 모음>=1 자음>=2 되면 출력하고 return
그렇게 계속 재귀 !!

코드 쓰기

백트래킹이니까 return해서 돌아오면 맨 끝에꺼 pop_back해서 지워주기!!!!!(부모 노드로 이동)
재귀 사용한다는 걸 계속 신경써야 할듯..

내 풀이

// BOJ-1759 암호 만들기
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 전역 변수 선언
int L = 0, C = 0;
vector<char> v; // 전체 C 벡터
vector<char> answer; // 답 벡터

// 백트래킹 함수
void back_tracking(vector<char> v, int moeum, int jaeum, int cur){
    // 답을 찾았을 때
    if (answer.size() == L && moeum >= 1 && jaeum >= 2){
        for(int i = 0; i < answer.size(); i++){ // 전체 answer 출력
            cout << answer[i];
        }
        cout << endl;
        return;
    }

    // 전체 C 내 for문
    for (int i = cur; i < C; i ++){
        // 문자가 모음일 때
        if (v[i] == 'a' || v[i] == 'e' || v[i] == 'i' || v[i] == 'o' || v[i] == 'u' ){
            answer.push_back(v[i]);
            back_tracking(v, moeum + 1, jaeum, i + 1);
            answer.pop_back();
        } else {
            // 문자가 자음일 때
            answer.push_back(v[i]);
            back_tracking(v, moeum, jaeum + 1, i + 1);
            answer.pop_back();
        }
    }
}

int main() {
    cin >> L >> C;
    for(int i = 0; i < C; i++ ){
        char t = 'a';
        cin >> t;
        v.push_back(t);
    }
    sort(v.begin(), v.end());
    
    back_tracking(v, 0, 0, 0);
}

풀고 나서 알게된 것

cur 부분 헷갈리지 말기…