백준 1759(암호 만들기)

www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

딱 봐도 브루트포스이다.

 

들어가고 안 들어가고, 총 15^2 의 시간복잡도가 소요된다. 따라서 잘 전처리하고, 들어갈때 안 들어갈 때를 구하면 된다. 

 

전처리라고 함은 사전식 배열로 바꾸어 줘야 한다. 

그냥 sort로 정렬을 하면 된다. 

 

그러고 나서 재귀로 돌리는데 조건을 잘 짜주자.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int L, C, mo, ja;
vector<char> v;
vector<char> ans;

void solve(int idx, int num) {
	if (num == L) {
		if (ja >= 2 && mo >= 1) {
			for (int i = 0; i < L; i++)cout << ans[i];
			cout << '\n';
		}
		return;
	}

	if (idx == C) {
		return;
	}
	bool moem = false;

	if (v[idx] == 'a' || v[idx] == 'e' || v[idx] == 'i' || v[idx] == 'o' || v[idx] == 'u') {
		moem = true;
	}
	if (moem)mo++;
	else ja++;
	ans.push_back(v[idx]);
	solve(idx + 1, num + 1);
	ans.pop_back();
	if (moem)mo--;
	else ja--;
	solve(idx + 1, num);
}

int main() {
	cin >> L >> C;

	for (int i = 0; i < C; i++) {
		char a;
		cin >> a;
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	solve(0, 0);
}