[ 백준 1759 ] 암호 만들기 (C++) - 조합, BackTracking

---

🔗 문제 링크

1759번: 암호 만들기

---

💡 문제 풀이 및 해석

1. 주어진 단어중 정해진 갯수를 뽑는 조합문제이다.
2. 조합으로 뽑은 다음에, 모음이 1개 이상, 자음이 2개 이상 들어갔는지 체크해주면 됩니다.

---

⭐️ 정답 코드 및 설명

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

int L, C;
bool visit[15];
vector<char> word;
set<string> answer;

void input() {
    cin >> L >> C;
    word = vector<char>(C);
    for (int i = 0; i < C; i++) {
        cin >> word[i];
    }
    sort(word.begin(), word.end());
}

bool isPassword(string password) {
    int passwordSize = password.size();
    bool aeiou = false;
    for (char c : password) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
            passwordSize--;
            aeiou = true;
        }
    }
    if (passwordSize >= 2 && aeiou) return true;
    return false;
}

void dfs(int cnt, int index, string password) {
    if (cnt == L) {
        if (isPassword(password)) cout << password << endl;
        return;
    }

    for (int i = index; i < C; i++) {
        password += word[i];
        dfs(cnt + 1, i + 1, password);
        password.pop_back();
    }
    return;
}

int main() {

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

---

🤔 문제 후기

처음에는 조합을 어떻게 했는지 기억나지 않았다. 오름차순으로 해야하니 아마 next_permutation을 사용해서 푸는 문제일 것으로 생각되는데, 솔직히 어떻게 쓰는지 기억이 잘 나지 않기도 하고, 간단한 조합이므로 그냥 구현해서 풀었다. 처음에는 i+1이 아닌 index+1을 줬었는데, 예제에 해당하는 답이 너무 이상하게 나와서 고민을 조금 하다가 생각해보니 a 다음은 b 다음은 c 다음은 d ... 순으로 가야하니 i+1을 넣어주는게 당연했다. 이 점을 제외하고는 문제를 푸는데 어려운 점은 없었다.