백준 BOJ 1759 - 암호 만들기

@WillKiss님의 추천으로 USACO를 천천히 밀어볼까 싶다.

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

1759번: 암호 만들기

 

 

예시로 나온 테스트케이스

a, t, c, i, s, w의 경우,

i번 문자열을 선택하거나 / 선택하지 않거나 의 두가지 선택지로 나눠

브루트포싱을 진행하면

전체 경우의 수는

2^6이 된다

 

C<=15 이므로

최대 경우의 수는 2^15 = 32768이고,

충분히 브루트포싱이 가능함을 알았으니

모든 경우에 대해 탐색을 진행하고

조건에 맞는 문자열 ( 길이가 L이고, 모음 한개 이상 자음 두개 이상 )

만을 출력하면 된다.

 

사전식으로 가능성 있는 암호이기 때문에,

주어지는 입력들을 미리 정렬해놓기를 권장한다

N^2정렬이어도 아무상관이없겠다만

그냥 std::sort() 쓰자

 

소스코드 펼쳐보기

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

int L,C;
char arr[15];
string mo = "aeiou";

bool chk(string s){
	int c_mo = 0;
	int c_ja = 0;
	
	for(char k : s){
		if(k=='a' || k=='e' || k=='i' || k=='o' || k=='u') c_mo++;
		else c_ja++;
	}
	
	if(c_ja>=2 && c_mo >=1) return true;
	else return false;
}

void dfs(string s, int idx){
	if(idx > C) return;
	
	if(s.length() == L){
		if(chk(s)) cout << s << "\n";
		return;
	}
	
	dfs(s+arr[idx], idx+1);
	dfs(s, idx+1);
	return;
}

int main(){
	cin >> L >> C;
	for(int i=0; i<C; i++){ cin >> arr[i]; }
	
	sort(arr, arr+C);
	
	dfs("", 0);
}