#BOJ 1759パスワードの作成

パスワードの作成

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	40718	19138	13273	44.743%

質問する
昨日、崔伯俊(チェ・ボジュン)助教が部屋の鍵をポケットに入れてソウルに持って行くのを忘れたというとんでもない状況に直面した助教たちは、702号に新しい保安システムを設置することにした.このセキュリティシステムは鍵ではなくパスワードで動作するシステムです.
暗号は異なるL個の小文字からなり、少なくとも1つの母音(a、e、i、o、u)と少なくとも2つの補助音からなる.また,配列を好む文字列の助教たちの傾向から,暗号を構成するアルファベットが暗号に増加する順に配列されていると推測される.すなわちabcは可能なパスワードであり、bacはそうではない.
新しいセキュリティシステムでは、助教たちが使用する可能性のあるパスワードにC種類の文字があるという.このアルファベットを手に入れた民植は、英植兄弟が助教たちの部屋に浸透するため、暗証番号を推測しようとした.C文字がある場合は、可能なすべてのパスワードを取得するためのプログラムを作成します.
入力
第1行は2つの整数L,Cを与える.(3≦L≦C≦15)次の行は、C文字をスペースで区切ります.与えられた文字は小文字で、重複はありません.
しゅつりょく
行ごとに1つ、可能なすべてのパスワードを出力しておきます.
入力例1
4 6
a t c i s w
サンプル出力1
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw
インプリメンテーション

/*
BOJ : https://www.acmicpc.net/problem/1759
backtracking 암호만들기
Versatile0010
*/


#include <bits/stdc++.h>
using namespace std;

int l, c; // c 개의 알파벳을 이용하여 l 길이의 암호 생성
char input_arr[30];
int arr[30];
bool isused[30];

bool check_aeiou(char alphabet)
{
	if (alphabet == 'a' || alphabet == 'e' || alphabet == 'i'
		|| alphabet == 'o' || alphabet == 'u')
		return true; // 모음이면 true 반환
	else return false;
}


void solve(int k)
{
	if (k == l) // 원하는 길이의 암호가 만들어지면
	{
		int aeiou_count = 0;
		int others_count = 0;
		bool isitgood = false;
		for (int i = 0; i < l; i++)
		{
			if (check_aeiou(input_arr[arr[i]]) == true) aeiou_count++;
			else others_count++;
		}
		if (aeiou_count >= 1 && others_count >= 2) isitgood = true;

		if (isitgood == true)
		{
			for (int i = 0; i < l; i++)
				cout << input_arr[arr[i]];
			cout << '\n';
			return;
		}
	}
	else
	{
		int start = 0;
		char temp = '0';
		if (k != 0) start = arr[k - 1] + 1;
		for (int i = start; i < c; i++)
		{
			if (isused[i] == false&&input_arr[arr[i]]!=temp)
			{
				isused[i] = true;
				arr[k] = i;
				temp = input_arr[arr[k]];
				solve(k + 1);
				isused[i] = false;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> l >> c;
	for (int i = 0; i < c; i++)
		cin >> input_arr[i]; // 입력받고
	cin.ignore();
	sort(input_arr, input_arr + c); // 정렬
	solve(0);

	return 0;
}

GIT : https://github.com/versatile0010/PS/blob/main/Backtracking/BOJ%201759%20%EC%95%94%ED%98%B8%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp