c++)백준 1759 - 암호 만들기

재귀호출을 통한 완전탐색을 통해 풀이했습니다.

 

풀이 과정

1. 생성되는 암호는 "알파벳이 증가하는 순서" 입니다.

따라서 sort 함수를 사용해서 입력받은 값을 미리 정렬시켜줍니다.

※ algorithm.h 헤더 사용

 

2. 입력받은 C개의 문자들로 만들 수 있는 모든 조합을 생각해야 합니다.

재귀호출을 통해 하나씩 문자열 길이를 늘려가면서 크기가 L이 되었을 때를 기저사례로 보고 출력할지 말지 판단합니다.

 

3. 암호에는 자음2개와 모음1개가 반드시 포함되어야 합니다.

만약 조건을 만족한다면 출력하고 아니라면 출력하지 않습니다.

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int L,C;
char strs[16];

void solution(vector <char> &s, int cnt) {
    if(s.size() == L) {
        int cnt1=0,cnt2=0;
        for(int i=0; i<L; i++) {
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') cnt1++;
            else cnt2++;
        }
        if(cnt1 >= 1 && cnt2 >= 2) {
            for(int i=0; i<s.size(); i++) printf("%c",s[i]);
            printf("\n");
        }
        return;
    }

    for(int i=cnt; i<C; i++) {
        s.push_back(strs[i]);
        solution(s,i+1);
        s.pop_back();
    }
}

int main()
{
    scanf("%d %d",&L,&C);
    char c;
    for(int i=0; i<C; i++) {
        scanf(" %c",&strs[i]);
    }
    vector < char > s;
    sort(strs, strs+C);
    solution(s,0);
}