[c++ 알고리즘] 백준 1759: 암호 만들기

 

문제를 읽어보니 Dfs 문제다. 예전에 풀었던 N과 M 문제가 생각난다.

 

Dfs 처럼 풀기 위해서는 알파벳 배열을 정렬시켜야 한다. 알파벳을 정렬시켜야 순서대로 암호를 만들라는 문제를 따를 수 있다.

 

std::sort로 char 형 배열을 정렬 시킬 수 있다.

 

또한 하나의 추가 조건이 있는데, 최소 하나의 모음과 두개의 자음으로 구성되어야 한다는 것이다.

 

본인은 이 문구를 보지 않고 넘어가서 바로 틀려버렸다.

 

조건은 전혀 어렵지 않다. 본인은 check 라는 bool 형 함수를 만들어서 조건에 맞지 않으면 false를 반환하는 함수를 만들었다.

그리고 Count == m, 즉 dfs에 자리수가 다 찼을 때, 값을 출력 해주는데 출력의 조건에 check 함수를 삽입하여 조건에 맞지 않으면 출력하지 않도록 하였다.

 

왜 골드인지 모르겠는 문제이다 !

 

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

char c[15] = {};
bool v[15] = {};
char list[15] = {};
int l, s;
void dfs(int n, int cnt);
bool check();

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	
	std::cin >> l >> s;

	for (int i{ 0 }; i < s; i++) {
		std::cin >> c[i];
	}
	std::sort(c, c + s);

	for (int i{ 0 }; i < s-l+1; i++) {
		dfs(i, 1);
	}
}

void dfs(int n, int cnt) {
	v[n] = true;
	list[cnt - 1] = c[n];

	if (cnt == l && check()) {
		for (int i{ 0 }; i < cnt; i++) {
			std::cout << list[i];
		}
		std::cout << "\n";
	}

	int tmp = n;
	while (tmp + 1 < s && cnt != l) {
		if (!v[tmp + 1]) dfs(tmp + 1, cnt + 1);
		tmp++;
	}

	v[n] = false;
}

bool check() {
	bool ans = false;
	int cnt = 0;
	for (int i{ 0 }; i < l; i++) {
		if (list[i] == 'a' || list[i] == 'e' || list[i] == 'i' || list[i] == 'o' || list[i] == 'u') {
			ans = true;
		}
		else {
			cnt++;
		}
	}

	if (cnt < 2 || !ans) {
		return false;
	}
	else return true;
}