문제 소개 📌

문제 링크 📢

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

문제 풀이 📝

암호를 만들 때 고려해야 할 점은 암호는 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있으며 알파벳이 증가하는 구성을 가진다는 것이다.
따라서 초기에 알파벳들을 입력받아 정렬을 하고 정렬된 알파벳들을 조합을 사용하여 뽑아내 모음과 자음의 개수를 검사해주며 조건에 맞는 암호를 출력해주면 되는 문제였다. 이 때 필자는 재귀적으로 조합을 구현했다!

코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

vector<char> cipher;
vector<char> v;
bool visited[30];
int L, C, vowel = 0, cons = 0; // 모음, 자음 개수를 세는 변수를 선언

bool isVowel(int i) // 모음인지?
{
	if (cipher[i] == 'a' || cipher[i] == 'e' || cipher[i] == 'i' || cipher[i] == 'o' || cipher[i] == 'u')
		return true;
	else return false;
}
void go()
{
	if (v.size() == L)
	{
		if (vowel >= 1 && cons >= 2)
		{
			for (int i = 0; i < L; i++)
			{
				cout << v[i];
			}
			cout << "\n";
		}		
		return; // 조건에 맞는 암호를 출력했으니 탈출!
	}
	for (int i = 0; i < C; i++)
	{
		if (!v.empty() && v.back() > cipher[i]) continue; // 조합 처리
		int idx = cipher[i] - 'a'; // 문자를 인덱스로 변환
		if (!visited[idx])
		{
			v.push_back(cipher[i]);
			visited[idx] = true;

			if (isVowel(i)) vowel++;				
			else cons++;

			go();

			if (isVowel(i)) vowel--;				
			else cons--;

			v.pop_back();
			visited[idx] = false;
		}
	}
}
int main()
{
	char c;
	cin >> L >> C;

	for (int i = 0; i < C; i++)
	{
		cin >> c;
		cipher.push_back(c);
	}
	sort(cipher.begin(), cipher.end());
	go();
		
	return 0;
}