[BOJ] 백준 1759번 암호 만들기 C++

문제

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

1759번: 암호 만들기

골드5짜리 백트래킹 문제치고는 매우 쉬웠다. 조합을 구하는 방법에 대해만 알고있으면 쉽게 풀 수 있다.

풀이

백트래킹 + 약간의 구현 문제이다.

암호 C개를 입력받고 정렬 시킨 후 조합을 돌려주었다. 이때 암호로서 사용할 수 있는지 조건을 판별해주기 위해 canPassword 함수를 만들어주어 조건을 만족하면 true 아니면 false를 반환하게 하여 true인 조건에 대해서만 암호를 출력할 수 있도록하여 문제를 해결할 수 있었다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int L, C;
char arr[16];
vector<char> password;
bool isused[16];

bool canPassword()
{
	int vowel = 0;
	int consonant = 0;

	for (int i = 0; i < password.size(); i++)
	{
		if (password[i] == 'a' || password[i] == 'e' || password[i] == 'i' || password[i] == 'o' || password[i] == 'u')
		{
			vowel++;
		}
		else
		{
			consonant++;
		}
	}

	if (vowel >= 1 && consonant >= 2)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void func(int idx, int cnt)
{
	if (cnt == L)
	{
		for (int i = 0; i < C; i++)
		{
			if (isused[i])
			{
				password.push_back(arr[i]);
			}
		}
		if (canPassword())
		{
			for (int j = 0; j < password.size(); j++)
			{
				cout << password[j];
			}
			cout << "\n";
			password.clear();
			return;
		}
		else
		{
			password.clear();
			return;
		}
	}

	for (int i = idx; i < C; i++)
	{
		if (!isused[i])
		{
			isused[i] = true;
			func(i + 1, cnt + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> L >> C;

	for (int i = 0; i < C; i++)
	{
		cin >> arr[i];
	}

	sort(arr, arr + C);

	func(0, 0);
}