[C/C++] 백준 #1759 암호 만들기(조합)

이번 문제는 조합을 이용하는 것입니다.  단지 조건이 좀 들어가 있습니다.  적어도 1개의 모음과 2개의 자음이 들어가야 합니다.

 

make a password

 

사실, 조합을 구한 다음에 모음의 개수를 세면, 그 외는 모두 자음이기때문에 손쉽게 풀 수 있습니다.

저는 재귀함수를 이용해서 풀었습니다.  모음의 개수를 따로 세어서 마지막에 검사를 했습니다.

 

재귀 함수를 사용하여 조합을 만들 수 있다면, 어렵지 않게 풀 수 있는 문제입니다.  암호의 길이가 길다면, 모음을 검사하는 비용이 클 수가 있기 때문에 주의가 필요하겠죠.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//-------------------------------------------------------
//    baekjoon #1759 - Making password
//        - by Aubrey Choi
//        - created at 2019-08-04
//-------------------------------------------------------
#include <stdio.h>
#include <algorithm>

void dup(char v[], char t[], int c, int s, int vowel, int m, int n)
{
    if(c==n)
    {
        if(vowel==0||n-vowel < 2) return;
        puts(t);
        return;
    }
    for(int i=s;i<m;i++)
    {
        t[c]=v[i];
        int s = v[i]=='a'||v[i]=='e'||v[i]=='i'||v[i]=='o'||v[i]=='u';
        dup(v, t, c+1, i+1, vowel+s, m, n);
    }
}

int main()
{
    int n, c;
    char v[16], t[16], ch;
    scanf("%d%d", &n, &c);
    for(int i=0;i<c;i++) { for(ch=getchar();ch<'a'||ch>'z';) ch=getchar(); v[i]=ch; }
    std::sort(v, v+c);
    t[n]=0;
    dup(v, t, 0, 0, 0, c, n);
}