BaekJoon 1759 암호만들기

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

소스결과 1988 KB / 0 ms

출처 Backjoon 

언어 C++ 17

 

설명

조금 간단한 백트래킹

0과 1로 이루어진 순열을 만들어 낸다 라고 생각하면 편하다.

모음이 1개 이상 , 자음이 2개 이상일 경우에만 출력하도록 조건을 걸면 된다.

 

알고리즘

1. 알파벳을 입력받아 - 'a'를 한뒤 사용할 수 있는 알파벳을 식별하는 배열에 넣는다.

2. 현재 알파벳을 사용 했으면 알파벳을 식별하는 배열의 값을 false로 바꾼후 함수를 재귀 호출한다.

3. 위치를 나타내는 pos가 암호의 길이 l 이 될때까지 반복 한다.

 

소스코드

#include <iostream>

using namespace std;

int l, c;

bool alpha[26];
char password[16];

void func(int pos, int last, int conson, int vow)
{
	if (pos == l)
	{
		if (conson > 1 && vow > 0)
			cout << password << '\n';
	}
	else
	{
		for (int i = last; i < 26; i++)
		{
			if (alpha[i])
			{
				bool vowol = false;
				if (i == 0 || i == ('e' - 'a') || i == ('i' - 'a') || i == ('o' - 'a') || i == ('u' - 'a'))
					vowol = true;

				password[pos] = i + 'a';
				alpha[i] = false;
				func(pos + 1, i, conson + !vowol, vow + vowol);
				password[pos] = 0;
				alpha[i] = true;
			}
		}
	}
}

int main()
{
	cin >> l >> c;

	for (int i = 0; i < c; i++)
	{
		char al;
		cin >> al;
		alpha[al - 'a'] = true;
	}

	func(0, 0, 0, 0);

	return 0;
}