BOJ 1759. 암호 만들기

• 문제링크 : https://www.acmicpc.net/problem/1759

---

문제 요약

주어진 C개의 서로 다른 소문자 중 L개를 골라 만들 수 있는 암호를 사전 순으로 모두 출력한다. 암호의 글자는 알파벳 순으로 증가해야 하고, 모음(a, e, i, o, u)을 하나 이상, 자음을 둘 이상 포함해야 한다.

---

1. 문제 해석

• 암호는 서로 다른 L개의 알파벳 소문자, 최소 한 개의 모음 + 최소 두 개의 자음
• 알파벳은 오름차순
• 문자의 종류는 C가지
• 암호를 모두 구하는 문제

문제를 요약하면 위와 같다. 문제의 이해를 정확히 하기위해 예시를 들어보면

• L = 4, C = 6
• 사용 가능한 알파벳: a t c i s w

이와 같은 조건이 주어졌을 때 가능한 경우(암호)는 다음과 같다.

acis acit aciw acst acsw actw aist aisw aitw astw cist cisw citw istw

이 문제를 푸는 방법은 크게 두 가지가 있을 수 있는데, 첫 번째는 모음 한개와 자음 두개를 무조건 포함하도록 하여 암호를 모두 구해보는 것이다. 두 번째는 모든 암호를 미리 만들어보고 그 중에서 모음 한개에 자음 두개를 포함한 것만 선택하는 것이다. 첫 번째 방법보다는 두 번째 방법이 훨씬 수월하므로, 두 번째 방법을 선택한다. 이처럼, 때로는 사고의 전환을 하여 반대로 생각하는 것이 더 쉬울 수도 있다.

어차피 오름차순으로 정렬된 결과만 채택하므로, 사용 가능한 알파벳을 미리 정렬한다.

a	c	i	s	t	w
o	o	o	o	o	o
x	x	x	x	x	x

그러면 이렇게 되는데, 각각 암호에 포함한다 or 안한다 로 경우의 수는 2^6가지이다. C가지 종류의 문자가 있다면 2^C 가지의 경우의 수가 나오게 된다. 이는 충분히 고려할만한 시간 복잡도를 가진다.

---

2. 문제 풀이

이 문제에서는 사용할 수 있는 알파벳의 제한이 있다. 따라서 제한된 알파벳의 길이를 넘어가는 경우에 정답을 찾을 수 없게 된다. 정답을 찾았다면 암호의 길이와 같게 된다. 이 두가지 경우가 아니라면 재귀호출을 통해서 다음 경우를 실행해야 한다.

• 먼저, 재귀를 모델링 하기 위해서 세 가지 경우를 생각해본다. 1) 정답을 찾은 경우는 길이가 n인 암호를 만든 경우이다. password의 길이 == n 2) 불가능한 경우는 사용할 수 있는 알파벳의 제한이 있으므로, 더이상 선택할 수 있는 알파벳이 없는경우에 불가능하다. i >= alpha의 크기 3) 다음 경우를 실행하는 것은 패스워드에 i번째를 사용하거나 사용하지 않는 경우를 모두 실행해보아야 한다.

• go(n, alpha, password, i) • n: 만들어야 하는 암호의 길이 • alpha: 사용할 수 있는 알파벳 • password: 현재까지 만든 암호 • i: 사용할지 말지 결정해야 하는 알파벳의 인덱스

정답은 찾은 경우를 생각해보면, passowrd의 길이가 n과 같으면 정답을 찾았다고 볼 수 있다.

• 정답을 찾은 경우 (문제의 조건에 맞는지 확인 과정은 여기서 필요함) • n == password.length()
• 불가능한 경우 • i >= alpha.size()
• 다음 경우 실행 • i번째 알파벳을 사용하는 경우 : go(n, alpha, password+alpha[i], i+1) • i번째 알파벳을 사용하지 않는 경우 : go(n, alpha, password, i+1)

void go(int n, vector<char> &alpha, string password, int i) {
  if (password.length() == n) {	// 정답을 찾은 경우
    if (check(password)) {
    	cout << password << '\n';
    }
    return;
  }
  if (i >= alpha.size()) return;	// 불가능한 경우
  go(n, alpha, password+alpha[i], i+1);	// 다음 경우 실행
  go(n, alpha, password, i+1);
}

이때 정답을 찾은 경우를 먼저 처리해 주어야 한다. 왜냐하면 불가능한 경우를 먼저 처리하게 되면, 경우에따라 정답을 찾은 경우를 처리하기도 전에 종료되어 버리기 때문이다.

bool check(string &password) {
  int ja = 0;
  int mo = 0;
  for (char x : password) {
    if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
    	mo += 1;
    } else {
    	ja += 1;
    }
  }
  return ja >= 2 && mo >= 1;
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool check(string &password) {
    int ja = 0;
    int mo = 0;
    for (char x : password) {
        if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
            mo += 1;
        } else {
            ja += 1;
        }
    }
    return ja >= 2 && mo >= 1;
}
void go(int n, vector<char> &alpha, string password, int i) {
    if (password.length() == n) {
        if (check(password)) {
            cout << password << '\n';
        }
        return;
    }
    if (i == alpha.size()) return;
    go(n, alpha, password+alpha[i], i+1);
    go(n, alpha, password, i+1);
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<char> a(m);
    for (int i=0; i<m; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());
    
    go(n, a, "", 0);

    return 0;
}