BaekJoon 1759번: 암호 만들기(C++)

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

1759번: 암호 만들기

풀이법

1) 백트래킹을 활용해서 해결할 수 있는 문제였다. 초기에 들어 오는 값을 sort하여 오름차순으로 만드는 작업이 필수적이다.

2) 이후 백트래킹을 활용하여 원하는 길이의 배열이 만들어 졌을 때, 모음의 개수가 1개 이상인지, 자음이 2개 이상인지 확인하여 출력을 진행하면 된다.

3) 출력 형식 때문에 틀렸습니다가 떠서 놀랬었던 문제이다. 꼭 문제를 제대로 읽도록 하자

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

int l, c;

vector<char> arr;
char ans[16];
bool visited[16];
void backtracking(int index, int cnt,int mo, int ja) {
	if (cnt == l)
	{
		if (mo >= 1 && ja >= 2) {
			for (int i = 1; i <= cnt; i++)
			{
				cout << ans[i];
			}
			cout << "\n";
		}
		return;
	}
	for (int i = index + 1; i <= c; i++) {
		if (!visited[i]) {
			visited[i] = true;
			ans[cnt + 1] = arr[i];
			if(arr[i]=='a' || arr[i]=='e'||arr[i]=='i'||arr[i]=='o'||arr[i]=='u')
				backtracking(i, cnt + 1,mo+1,ja);
			else
				backtracking(i, cnt + 1, mo, ja+1);
			visited[i] = false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> l >> c;
	arr.push_back(0);
	for (int i = 1; i <= c; i++) {
		char d; cin >> d;
		arr.push_back(d);
	}
	sort(arr.begin(), arr.end());
	backtracking(0, 0,0,0);
}