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

문제 링크

1759번: 암호 만들기

문제 요약

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

접근 방법

L, C가 모두 15정도입니다. $_nC_k$에서 $n$이 15정도이면 그 값은 $k$와 상관 없이 10000을 넘지 못합니다.

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

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

코드

#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;
}