(cpp) Baekjoon 1759번 문제 ‘암호 만들기 ‘ - 수학, 브루트포스, 백트래킹, 조합론

on Programming Languages

Baekjoon 1759번 문제 ‘암호 만들기 ‘ - 수학, 브루트포스, 백트래킹, 조합론

문제

예제입력1에 대한 문제풀이

입력

4 6
a t c i s w

모음 : a i
자음 : t c s w
위의 자모음 각각을 오름차순 정렬하면 아래와 같다.
모음 : a i
자음 : c s t w

암호의 조건인 모음 1개 이상, 자음 2개 이상을 만족하는 암호를 바로 만들기보단 입력된 총 6개의 알파벳으로 가능한 모든 암호 조합을 만들고 조건에 해당하는 경우만 출력한다. 가능한 모든 암호 조합은 아래와 같다.

4 6
a t c i s w
a c i s t w
a
ac
aci
acis
acist
acistw
acisw
acit
acitw
aciw
acs
acst
acstw
acsw
act
actw
acw
ai
ais
aist
aistw
aisw
ait
aitw
aiw
as
ast
astw
asw
at
atw
aw
c
ci
cis
cist
cistw
cisw
cit
citw
ciw
cs
cst
cstw
csw
ct
ctw
cw
i
is
ist
istw
isw
it
itw
iw
s
st
stw
sw
t
tw
w

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int len, word; //len : 암호길이, word : 문자의 종류
char alp;
vector<char> moja,password;


bool check_password() {
	int mo_num = 0;
	for (int i = 0; i < len; i++) {
		if (password[i] == 'a' || password[i] == 'e' || password[i] == 'i' || password[i] == 'o' || password[i] == 'u')
			mo_num++;
	}
	if (mo_num >= 1 && len - mo_num >= 2) {
		return true;
	}
	return false;
}

void make_password(int d) {
	if (password.size() == len) {
		if (check_password()) {
			for (int s = 0; s < len; s++) {
				cout << password[s];
			}
			cout << '\n';
		}
	}
	for (int i = d; i < word; i++) {
		password.push_back(moja[i]); //a
		make_password(i + 1);
		password.pop_back();
	}
	return;
}




int main() {
	cin >> len >> word;
	for (int i = 0; i < word; i++) {
		cin >> alp;
		moja.push_back(alp);
	}
	sort(moja.begin(), moja.end());
	make_password(0);
}

가능한 모든 조합 뽑는 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
#include<algorithm>
using namespace std;

//1759번
//암호 조건
//1. 최소 한 개의 모음, 최소 두 개의 자음
// 1-1. 모음 갯수 세기 
// 1-2. 만약 모음이 3개면 모음 1개인 경우부터 3개인 경우까지 가능한 모든 조합 구하기
// 1-3. 모음 m개, 자음 len-m개 (m=1...)
//2. 증가하는 순서 (abc 가능, bac 불가능)
// a e f d 로 3자리 만들기
// 정렬 :  a d e f
// 모음 (a e) 자음(d f)

int len, word; //len : 암호길이, word : 문자의 종류
char alp;
vector<char> moja, password;


bool check_password() {
	int mo_num = 0;
	for (int i = 0; i < len; i++) {
		if (password[i] == 'a' || password[i] == 'e' || password[i] == 'i' || password[i] == 'o' || password[i] == 'u')
			mo_num++;
	}
	if (mo_num >= 1 && len - mo_num >= 2) {
		return true;
	}
	return false;
}

void make_password(int d) {

	for (int s = 0; s < password.size(); s++) {
		cout << password[s];
	}
	cout << '\n';

	for (int i = d; i < word; i++) {
		password.push_back(moja[i]); //a
		make_password(i + 1);
		password.pop_back();
	}
	return;
}




int main() {
	cin >> len >> word;
	for (int i = 0; i < word; i++) {
		cin >> alp;
		moja.push_back(alp);
	}
	sort(moja.begin(), moja.end());
	for (int k = 0; k < word; k++) {
		cout << moja[k] <<" ";

	}
	make_password(0);



	//while (!mo.empty()) {
	//	cout << mo.top(); //o u i e a
	//	mo.pop();
	//}
	//cout << '\n';
	//while (!ja.empty()) {
	//	cout << ja.top(); //o u i e a
	//	ja.pop();
	//}
}
  • 딱 원하는 자릿수의 암호를 바로 만들지 않고 일단 가능한 모든 조합을 만든 후에 조건에 해당하는 경우에만 출력한다.