문제 출처

1. 문제설명

  • C개의 문자에서 길이가 L인 문자열을 만든다.
  • 단, 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어야 한다.
  • 조건을 만족하는 모든 경우를 사전순으로 출력하라



2. 알고리즘 설계

  • DFS 문제이다.
  • 글자를 사전순으로 놓아주면서 L이 될 때까지 놓는다.
  • 길이가 L이 되면,
    • 모음, 자음의 개수를 세는 변수를 각각 선언한다.
    • 문자를 하나씩 탐색하면서, 카운팅한다.
    • 카운팅 된 변수가 조건을 만족한다면 출력한다.



3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 26;
int L, C;
char pw[SZ], v[SZ];

void solve(int cnt, int s) {
	if(cnt == L) {
		string str = "";
		int cnt1=0, cnt2=0;
		for(int i=0; i<L; i++) {
			if(v[i] == 'a' || v[i] == 'e' || v[i] == 'i' || v[i] == 'o' || v[i] == 'u') cnt1++;
			else cnt2++;
			str += v[i];
		}
		
		if(cnt1 >= 1 && cnt2 >= 2)
			cout << str << '\n';

		return;
	}

	for(int i=s; i<C; i++) {
		v[cnt] = pw[i];
		solve(cnt+1, i+1);
		v[cnt] = '\0';
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> L >> C;
	for(int i=0; i<C; i++)
		cin >> pw[i];

	sort(pw, pw+C);

	solve(0, 0);
    return 0;
}