1759번. 암호 만들기

최근 풀이 241113

1) 백트래킹으로 가야 한다.
2) 11퍼센트에서 틀리는데, 다시 문제를 보면, 모음은 반드시 1개, 자음은 반드시 2개 이상이어야 한다는 조건이 있다. 이를 유념해서 작성하자.

---

풀이 전략

1) 문제를 보고, 조합으로 진행해야 겠다는 생각을 함.
2) 모음 1개, 자음 2개 이상일 경우를 체크하고, 출력하는 방식으로 진행함.

코드

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


// 22:58 ~ 23:14
//조합 : combination
int l, c;
vector<char>res;

void combi(vector<char>&v, int start)
{
	if (res.size() == l)
	{
		int mo = 0;
		int ja = 0;
		for (auto iter : res)
		{
			//조건 확인 하지
			// 최소 모음 1개, 자음 2개 있어야 함.
			if (iter == 'a' || iter == 'i' || iter == 'e'
				|| iter == 'o' || iter == 'u')
			{
				++mo;
			}
			else
			{
				++ja;
			}
		}

		if (mo >= 1 && ja >= 2)
		{
			for (auto iter : res)
			{
				cout << iter;
			}
			cout << endl;
		}
	}
	


	for (int i = start; i < v.size(); ++i)
	{

		res.push_back(v[i]);
		combi(v, i + 1);
		res.pop_back();
	}

}

int main() 
{
	// 서로 다른 l개의 알파벳 소문자.
	// 최소 한개의 모음, 최소 2개의 자음으로 구성됨.

	//오름차순 정렬 

	
	cin >> l >> c;

	vector<char>v(c);

	for (int i = 0; i < c; ++i)
	{
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	// 모음에서 최소 1개를 꺼내야함. 
	// 최소 2개의 자음을 꺼내야 함.
	// a c i s t w

	// 어떻게 할 것이냐면? 
	// combi 으로 돌리면서 
	// 자음과 모음의 숫자를 카운팅 , 
	// 그리고 조건으로 처리하자. 
	combi(v, 0);
 }