백준 1759번 암호 만들기

< 백준 1759번 암호 만들기 - 마포 코딩박 >

사용한 알고리즘: 완전탐색


 C개의 주어진 글자로 각 글자가 사전순으로 증가하는 규칙을 가진 L길이의 단어를 몇개나 만들 수 있는지 출력하는 문제이다.
 주어진 글자들을 정렬한뒤, 모두 만들어 보아 문제를 해결했다.

문제풀이는 다음과 같다.
(1) (코드: 38)
 주어지는 글자들을 배열로 저장한 후 sort 한다. 각 글자들은 알파벳순으로 정렬된다.

(2) (코드: 10~31)
 만들어진 단어 길이(pos) , 넣은 글자(prev) , 만든 단어의 모음수(consonant), 자음수( vowel) 를 저장하며 단어를 만들어본다.
 넣을 수 있는 글자는 과정(1) 에서 알파벳 순으로 정렬해 놓았으므로, 순서 그대로 단어를 만들면 된다.
 만든 단어길이가 L이 되면 해당 단어를 출력한다.

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int L, C;
	char A[15], P[16];
	// false: 자음 , true: 모음
	bool isVowel[26];
	void back(int pos, int prev, int consonant, int vowel){
	// 단어 길이가 L일때
	if(pos == L){
	// 최소 2개 모음, 1개 자음
	if(consonant >=2 && vowel >= 1){
	for (int i = 0; i < L; ++i)
	cout << P[i];
	cout << '\n';
	return;
	}
	}
	// 사전순으로 글자가 정렬된 상태이므로 하나씩 골라봄
	for (int i = prev+1; i < C; ++i){
	char now = A[i];
	P[pos] = now;
	if(isVowel[i])
	back(pos+1, i, consonant, vowel+1);
	else
	back(pos+1, i, consonant+1, vowel);
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> L >> C;
	for (int i = 0; i < C; ++i)
	cin >> A[i];
	// 각 글자 사전순 정렬
	sort(A, A+C);
	for (int i = 0; i < C; ++i){
	if(A[i] == 'a' || A[i] == 'e' || A[i] == 'i' || A[i] == 'o' || A[i] == 'u')
	isVowel[i] = true;
	}
	back(0,-1,0,0);
	return 0;
	}

view raw BOJ 1759.cpp hosted with ❤ by GitHub