백준 1759 (암호 만들기)

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

1759번: 암호 만들기

 

해당 문제는 정수 L, C가 주어지며 C개의 문자들이 주어지면 해당 문자 중 L개의 문자를 가지고 조합을 만들어 해당 조합이 오름차순일때만 출력하는 문제이다. 추가적인 조건은 다음과 같다.

1. 출력 형태역시 문자조합의 오름차순으로 출력을 해야한다.

2. L개의 길이를 가지는 문자열은 항상 1개 이상의 모음, 2개 이상의 자음이 포함되어야 한다.

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

using namespace std;
int l, c;

string str;
string results;
int used[16];

// 자음 모음 체크 함수
int checkE(char i){
	if (i == 'a' || i == 'e' || i == 'i' || i == 'o' || i == 'u') return 1;
	else return 2;
}

void dfs(int level, int mCnt, int jCnt){
	if (level == l){
		if (mCnt >= 1 && jCnt >= 2){
			cout << results << endl;
		}
		return;
	}

	for (int i = 0; i < c; ++i){
		int n = results.length();
		if (used[i] == 1)continue;
		if (n > 0 && results[n - 1] > str[i]) continue;

		used[i] = 1;
		results.push_back(str[i]);
		// 재귀시 모음과 자음인 경우를 나누어 재귀 수행 
		if (checkE(str[i]) == 1) dfs(level + 1, mCnt + 1, jCnt);
		else dfs(level + 1, mCnt, jCnt + 1);
		results.pop_back();
		used[i] = 0;
	}

}

int main(){
	freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> l >> c;

	for (int i = 0; i < c; ++i){
		char tmp;
		cin >> tmp;
		str.push_back(tmp);
	}

	// 출력시 오름차순으로 출력하기 때문에 처음에 sorting 한 뒤 DFS 수행
	sort(str.begin(), str.end());
	dfs(0,0,0);

}