백준 1759 - 암호 만들기 (c++)

백준 1759 - 암호 만들기

문제 링크

생각 및 접근

• 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.라는 말에서, DFS 방식으로 풀면 되겠다는 생각을 했다.
  • 암호의 재료가 되는 문자들을 sort한 뒤 DFS를 하면, L개만큼 고른 뒤의 그 문자열을 보면 모두 사전식일 것이다.
• 암호의 재료가 되는 문자들을 받은 뒤에, 그 문자들로 DFS를 진행하면 된다. 단, 내가 원하는 만큼 골랐을 때(문제에서는 L만큼 골랐을 때) 자음과 모음의 갯수를 세서 암호의 가능성이 있는 문자열인지 확인해야 한다.

코드

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

vector<char> v;
vector<int> visit;
int l, c;
char temp;

void dfs(int len, int idx){
    if(len == l){
        int con = 0, vow = 0;
        for(int i = 0; i < v.size(); i++){
            if(visit[i] == 1){
                if(v[i] == 'a' || v[i] == 'e' || v[i] == 'i' || v[i] == 'o' || v[i] == 'u')
                    vow++;
                else
                    con++;
            }
        }
        if(con >= 2 && vow >= 1){
            for(int i = 0; i < v.size(); i++){
                if(visit[i] == 1)
                    cout << v[i];
            }
            cout << endl;
        }
    }
    else{
        for(int i = idx; i < v.size(); i++){
            visit[i] = 1;
            dfs(len + 1, i + 1);
            visit[i] = 0;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> l >> c;
    for(int i = 1; i <= c; i++){
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end());
    visit.assign(v.size(), 0);

    dfs(0, 0);
}

채점 결과