[백준 C++] 1759 암호 만들기 - 조합론

1759번: 암호 만들기

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

int L, C;
vector<char> Alphabets;

void DFS(string PW, int CurAlphabetIndex)
{
	if (PW.size() == L)
	{
		int Parent = 0;
		int Child = 0;
		for (int i = 0; i < L; ++i)
		{
			if (PW[i] == 'a'
				|| PW[i] == 'e'
				|| PW[i] == 'i'
				|| PW[i] == 'o'
				|| PW[i] == 'u')
			{
				++Parent;
			}
			else
			{
				++Child;
			}
		}
		if (Parent >= 1
			&& Child >= 2)
		{
			cout << PW << '\n';
		}

		return;
	}
	else if (CurAlphabetIndex == C)
	{
		return;
	}

	string OriginPW = PW;
	string NewPW = PW;
	NewPW.push_back(Alphabets[CurAlphabetIndex]);

	DFS(NewPW, CurAlphabetIndex + 1);
	DFS(OriginPW, CurAlphabetIndex + 1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> L >> C;

	Alphabets.reserve(C);
	for (int i = 0; i < C; ++i)
	{
		char Alphabet;
		cin >> Alphabet;
		Alphabets.emplace_back(Alphabet);
	}

	sort(Alphabets.begin(), Alphabets.end());

	DFS("", 0);
}

---

 

L개의 알파벳 중에 순서를 고려하지 않고 C개를 선택하는 모든 경우를 출력하는 조합론 문제입니다.

풀이과정은 다음과 같습니다.

 

1. pw를 사전 순으로 나열해서 출력하기 위해서 입력 받은 알파벳 데이터를 오름차순 정렬해줍니다.

2. DFS를 이용해서 가장 앞의 알파벳부터 완전탐색을 진행합니다. (pw에 해당 알파벳을 포함하는 경우, 포함하지 않는 경우 탐색)

3. pw의 길이가 모두 채워졌을 때 조건에 맞는 경우(모음 1개 이상, 자음 2개 이상) 출력합니다.

4. 재귀함수의 breakpoint를 설정해줍니다.