[BOJ] 1759 - 암호 만들기

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

---

[알고리즘풀이]

먼저 사용 가능한 문자들을 Sort한 후, 중복 없이 백트레킹을 이용해 N개를 뽑는다. 그 후, 모음과 자음 개수를 체크하고 조건에 부합하면 출력 / 아니면 종료하면 된다.

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

using namespace std;

void bt(vector<char>, int);

int n, m;
char c[16] = {};

int main(void) {
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> c[i];
	sort(c, c + m);
	for (int i = 0; i < m; i++) {
		vector<char> l;
		l.push_back(c[i]);
		bt(l, i);
		l.pop_back();
	}
}

void bt(vector<char> l, int start) {
	if (l.size() == n) {
		int c = 0;
		for (int i = 0; i < n; i++) {
			if (l[i] == 'a' || l[i] == 'e' || l[i] == 'i' || l[i] == 'o' || l[i] == 'u')
				c++;
		}
		if (c < 1 || n - c < 2)
			return;
		for (int i = 0; i < n; i++)
			cout << l[i];
		cout << '\n';
		return;
	}
	for (int i = start + 1; i < m; i++) {
		l.push_back(c[i]);
		bt(l, i);
		l.pop_back();
	}
	return;
}

---