암호 만들기 (feat. 백준, 1759번)

암호 만들기
https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
int L, C;
char arr[15];
bool visit[15];
set<string> ans;
void dfs(string str, register int idx){
    if(str.size() == L)
    {
        register int v1 = 0, v2 = 0;
        for(auto& ch : str)
            if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
                ++v1;
            else
                ++v2;
        if(v1 >= 1 && v2 >= 2)
            ans.insert(str);
        return;
    }
    for(register int i = idx; i < C; ++i)
        if(!visit[i]){
            visit[i] = true;
            dfs(str + arr[i], i + 1);
            visit[i] = false;
        }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> L >> C;
    for(register int c = 0; c < C; ++c)
        cin >> arr[c], visit[c] = false;
    sort(arr, arr + C);
    dfs("", 0);
    for(auto& str : ans)
        cout << str << "\n";
    return 0;
}
// *&)*@*

 

반응형

1. dfs를 이용하여 조합을 구하는 문제입니다.
2. 단 정답의 조건 (1개 이상의 모음, 2개 이상의 자음) 에 해당되는 경우에만 정답이 됩니다.