BOJ 1759

암호만들기

문제출처

문제 해석

  • 서로 다른 L개의 알파벳을 어떠한 조건에 부합되도록 조합하여 암호를 만드는 문제입니다.
  • 암호가 되기 위한 조건은 다음과 같습니다.
    1. 알파벳이 증가하는 순서로 배열되어있어야 합니다.
    2. 최소 모음 1개와 자음 2개로 구성되어있어야 합니다.

설계(10)

  • L,C <= 15이므로 완전탐색으로 충분히 해결할 수 있습니다.
  • 조건 1에 부합하는 암호를 만들기 위해서 먼저 주어진 알파벳들을 사전순으로 정렬합니다.
  • 완전탐색으로 알파벳들의 조합을 찾고, 해당 문자열이 가지고 있는 자음과 모음의 개수를 저장합니다.
  • 완성된 문자열이 L개일 경우 2번 조건에 부합한 지 확인 후, 출력합니다.

구현(10)

코드
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 15

int L, C;
char words[MAXN];
void dfs(int now, int cnt, int vols, int cons, string str) {
	if (cnt == L) {
		if (vols >=1 && cons >= 2) cout << str << "\n";
		return;
	}
	for (int i = now; i < C; i++) {
		if (words[i] == 'a' || words[i] == 'e'
			|| words[i] == 'i' || words[i] == 'o'
			|| words[i] == 'u') {
			dfs(i + 1, cnt + 1, vols + 1, cons, str + words[i]);
		}
		else dfs(i + 1, cnt + 1,vols,cons+1, str + words[i]);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> L >> C;
	for (int i = 0; i < C; i++) {
		cin >> words[i];
	}
	sort(words, words + C);
	dfs(0, 0, 0, 0,"");
	return 0;
}
디버깅
  • 처음에 2번 조건을 고려하지 않아서 WA가 나왔습니다.
  • 자음과 모음의 개수를 카운트하기 위한 매개변수를 추가 구현하였습니다.
제출결과
  • 0ms

마무리

  • 기본적인 완전탐색 문제였습니다. 사전순으로 먼저 정렬하는 것이 중요 요소였습니다.