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

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

1759번: 암호 만들기

브루트포스 알고리즘 + 백트래킹으로 구현하였다.

우선, 알파벳을 오름차순으로 정렬 한 후 백트래킹을 통해 정렬된 순서를 유지하면서 L개를 선택하는 모든 경우를 탐색하였다. 그 후, 조건에 맞으면 출력하였다. 

 

백트래킹 함수에서 처음엔 매개변수를 cnt로만 두었다. 하지만, 그렇게 하면 정렬된 순서를 유지하지 못하고 뽑았던 문자 조합을 순서가 바뀐 모양으로 또 선택하게 되서 비효율적이었다.

따라서, 현재 위치와 선택 한 문자의 갯수를 나타내는 두개의 매개변수를 사용하여 해결하였다.

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

int L, C;
vector<char> c;
vector<char> tmp;
int visit[26];

//백트래킹 
void solve(int cur,int cnt) { //정렬된 순서를 유지하되 중복없이 선택하기 위해 두개의 매개변수 사용(현재위치,선택개수)
	if (cnt == L) {
		int cnt = 0;
		string s = "";
		for (int i = 0; i < L; i++){
			if (tmp[i] == 'a' || tmp[i] == 'e' || tmp[i] == 'i' || tmp[i] == 'o' || tmp[i] == 'u') cnt++;
			s.push_back(tmp[i]);
		}
		if (1 <= cnt && L - cnt >= 2) cout << s << endl; //모음 1개이상 & 자음 2개이상
		return;
	}
	for (int i = cur; i < C; i++) {
		int index = c[i] - 'a';
		if (!visit[index]) {
			visit[index] = 1;
			tmp.push_back(c[i]);
			solve(i+1,cnt + 1);
			tmp.pop_back();
			visit[index] = 0;
		}
	}
}

int main() {
	cin >> L >> C;
	char n;
	for (int i = 0; i < C; i++) {
		cin >> n;
		c.push_back(n);
	}
	sort(c.begin(), c.end()); //선 정렬
	solve(0,0);
}