[백준 / BOJ] C++ 1759 암호 만들기

1759번: 암호 만들기

 

문제

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

 

풀이

C개의 문자를 입력받아 길이가 L인 문자열을 구하는 문제다. 단, 문자열의 문자는 오름차순이어야 하며 모음이 최소 한 개, 자음이 최소 2개 포함하고 있어야 한다. 가능한 모든 문자열을 사전순으로 출력하는 문제.

 

백트래킹으로 풀었다.

문자열의 문자가 오름차순이어야 하므로 입력받은 문자들을 정렬해 주었다. 길이를 cnt로 두어 dfs 함수를 구현해 주었다.

 

cnt == L이 되면 ans 배열을 확인하여 조건을 만족하면 출력해 주고 return 한다.

cnt != L이면 입력받은 문자들을 차례대로 확인하며 아직 방문하지 않았고 이전 문자보다 사전순으로 뒤인 경우에 먼저 해당 문자를 방문 처리하고 ans 배열의 cnt 인덱스에 문자를 넣어준다. 그리고 다음 문자를 탐색하기 위해 dfs(cnt + 1)을 호출한다. 탐색이 끝난 후엔 방문 처리를 취소한다.

 

추가) 범위가 15밖에 안되기 때문에 브루트포스로 풀 수도 있다. 조합으로 가능한 모든 경우를 구하고 조건에 맞는 문자열만 출력하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int l, c;
vector<char> v(15, '~'), ans(15, ' ');
vector<int> visited(15, 0);

void dfs(int cnt) {
  if (cnt == l) {
    int tmp = 0;
    for (int i = 0; i < l; i++)
      if (ans[i] == 'a' || ans[i] == 'e' || ans[i] == 'i' || ans[i] == 'o' || ans[i] == 'u')
        tmp++;
    if (tmp >= 1 && l - tmp >= 2) {
      for (int i = 0; i < l; i++)
        cout << ans[i];
      cout << '\n';
    }
    return;
  }
  for (int i = 0; i < c; i++) {
    if (!visited[i] && ans[cnt - 1] < v[i]) {
      visited[i] = 1;
      ans[cnt] = v[i];
      dfs(cnt + 1);
      visited[i] = 0;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> l >> c;
  for (int i = 0; i < c; i++)
    cin >> v[i];
  sort(v.begin(), v.end());
  dfs(0);
  return 0;
}