[백준] 1759 - 암호 만들기 (C++)

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

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며, 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성돼 있다. 암호를 이루는 알파벳은 암호에서 증가하는 순서로 배열돼 있고, 암호에 사용한 문자의 종류는 C가지이다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 3 ≤ L ≤ C ≤ 15

 

암호에 사용된 알파벳은 증가하는 순서로 배열돼야 하기 때문에 C가지의 문자들을 입력 받은 뒤, 정렬해 저장해야 한다. 조건에 맞춰 문자를 붙이면서 백트래킹 함수를 진행해야 하고, 만들어진 문자열이 길이가 L이고 자음이 최소 1개 이상, 모음이 최소 2개 이상이면 출력하도록 종료 조건을 만들었다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. L, C 입력 받기
2. C가지의 문자 입력 받고 오름차순으로 정렬하기
3. 백트래킹 함수 진행
   1. 종료 조건은 만들어진 문자열의 길이가 L일 때,
      1. 자음이 최소 1개, 모음이 최소 2개인 문자열이라면 출력 / 아니면 함수 종료
   2. idx 변수를 통해 이전에 쓴 알파벳보다 앞에 있는 알파벳은 쓰지 않도록 반복문을 진행
      1. idx번째 문자가 모음인지 자음인지에 따라 dfs() 함수의 파라미터를 다르게 넣기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1~2회차

• 문자를 미리 정렬해놓기 때문에 굳이 set을 사용할 필요 없음 → 백트래킹 함수에서 정답 문자열을 출력하도록 수정
• 시간초과
  • 백트래킹 함수에서 반복문을 0부터 C까지 진행하기 때문에 시간 초과가 발생함 → 마지막으로 방문한 문자의 idx를 백트래킹 함수의 파라미터로 넘겨 반복문을 idx부터 C까지 진행하도록 수정 (visit 배열 삭제)

 

---

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int l,c;
vector<char> v;

void dfs(int dep, int idx, int a, int b, string tmp) {
    if (dep==l) {
        if (a>=1 && b>=2) cout << tmp << '\n';
        return;
    }

    for (int i=idx; i<c; i++) {
        char ch = v[i];
        if (ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u') dfs(dep+1,i+1,a+1,b,tmp+ch);
        else dfs(dep+1,i+1,a,b+1,tmp+ch);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> l >> c;
    char ch;
    for (int i=0; i<c; i++) {
        cin >> ch;
        v.push_back(ch);
    }
    sort(v.begin(),v.end());

    dfs(0,0,0,0,"");
}