BOJ 1759. 암호 만들기

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

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

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;
}