백준 1759 암호 만들기

문제 링크: https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

주어진 알파벳으로 가능한 조합들을 다 만들어보고, 각 조합마다 자음과 모음갯수를 세서 조건에 맞으면 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;
 
int l, c;
char a[16], ans[16];
 
void solve(int start, int idx) {
    if(idx == l) {
        int v_cnt = 0, c_cnt = 0;
        for(int i = 0; i < l; i++) {
            if(ans[i] == 'a' || ans[i] == 'e' || ans[i] == 'i' || ans[i] == 'o' || ans[i] == 'u')
                v_cnt++;
            else
                c_cnt++;
        }
        if(v_cnt >= 1 && c_cnt >= 2) {
            for(int i = 0; i < l; i++)
                cout << ans[i];
            cout << '\n';
        }
        return;
    }
 
    for(int i = start; i < c; i++) {
        ans[idx] = a[i];
        solve(i + 1, idx + 1);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> l >> c;
    for(int i = 0; i < c; i++) cin >> a[i];
    sort(a, a + c);
    solve(0, 0);
    return 0;
}
 

조합을 이용하고 있으므로 시간복잡도가 O(2^c)인 코드를 아래와 같이 구현할수 있다.

#include <bits/stdc++.h>
using namespace std;
 
int l, c;
char a[16], ans[16];
 
void solve(int start, int idx) {
    if(idx == l) {
        int v_cnt = 0, c_cnt = 0;
        for(int i = 0; i < l; i++) {
            if(ans[i] == 'a' || ans[i] == 'e' || ans[i] == 'i' || ans[i] == 'o' || ans[i] == 'u')
                v_cnt++;
            else
                c_cnt++;
        }
        if(v_cnt >= 1 && c_cnt >= 2) {
            for(int i = 0; i < l; i++)
                cout << ans[i];
            cout << '\n';
        }
        return;
    }
    if(start >= c) return;
 
    ans[idx] = a[start];
    solve(start + 1, idx + 1);
    solve(start + 1, idx);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> l >> c;
    for(int i = 0; i < c; i++) cin >> a[i];
    sort(a, a + c);
    solve(0, 0);
    return 0;
}