[1759번] 암호 만들기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 백트래킹(Backtracking) 

[2661번] 좋은 수열 :: http://www.crocus.co.kr/657

위의 문제를 풀고 이 문제를 풀어도 도움이 많이 되고, 이 문제를 풀고 위의 문제를 풀어도 도움이 많이 된다.

백트래킹에 대한 전반적인 지식이 있어야 한다.

백트래킹도 dfs의 일종이지만, dfs를 자유자제로 이용할 수 있지 않는한 백트래킹을 생각해내기가 어렵다.

원리는 다음과 같다.

우선 char 배열에 문자를 받아주고, 정렬을 해준다.(정렬을 해야 사전 순으로 나타날 수 있다.)

스트링의 크기가 n이 될 때까지 순차적으로 계속 담아준다.

크기가 n이 되었을 때 자음, 모음이 각각 2개 1개 이상씩 있는지 검사해주고 없다면 return을 있다면 출력을 해준다.

백트래킹중에 파라미터로 str, 자음, 모음 수를 추가해준 것이니 return을 받게되면 다시 그 다음값을 넣어주는 방식을 취하게 된다.

이 문제를 접한 코더들이라면 위의 추천 문제는 꼭 풀어봤으면 하는 문제이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
 
using namespace std;
 
int n, m;
char arr[20];
 
void backTracking(int pos, string str, int ja, int mo)
{
    if (str.size() == n)
    {
        if (ja < 2 || mo < 1)
            return;
        
        cout << str << endl;
    }
 
    for (int i = pos; i < m; i++)
    {
        if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
            backTracking(i + 1, str + arr[i], ja, mo + 1);
        else
            backTracking(i + 1, str + arr[i], ja + 1, mo);
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++)
        cin >> arr[i];
 
    sort(arr, arr + m);
 
    backTracking(0,"",0,0);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>