[C++] 백준 1759번: 암호 만들기

문제 링크

1759번: 암호 만들기

문제 요약

C개의 알파벳 중에서, 서로 다른 L개의 알파벳 소문자로 구성된 암호를 만들어야 한다. 이 암호는 최소한 한 개의 모음과 두 개의 자음을 포함해야 한다. 이때 가능한 암호들을 사전순으로 출력해야 한다.

접근 방법

L, C가 모두 15정도입니다. $_nC_k$

따라서 그냥 가능한 모든 조합을 구하고, 자음과 모음의 수를 세줘서 조건을 충족하면 결과로 출력해주면 됩니다.

문제에서 사전순으로 출력해야 한다는 조건이 있었는데, 최초에 값을 입력받고 정렬한 다음에 백트래킹을 수행하면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int l, c;
vector<char> v;
string str;
bool visited[16];

void func(int cnt, int idx)
{
	if (cnt == l)
	{
		int v_cnt = 0, c_cnt = 0;

		for (int i = 0; i < l; i++)
		{
			if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u')
				v_cnt++;
			else
				c_cnt++;
		}

		if (v_cnt >= 1 && c_cnt >= 2)
			cout << str << '\n';

		return;
	}

	for (int i = idx; i < c; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			str.push_back(v[i]);
			func(cnt + 1, i + 1);
			visited[i] = false;
			str.pop_back();
		}
	}
}

int main(void)
{
	cin >> l >> c;

	v.resize(c);
	for (int i = 0; i < c; i++)
		cin >> v[i];

	sort(v.begin(), v.end());
	func(0, 0);

	return 0;
}