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

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

1759번: 암호 만들기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<char>v;
vector<char>result;
int L, C;

void func(int size, int cur)
{
    if(size==L)
    {
        int consonant = 0, vowel = 0;
        for(int i=0; i<result.size(); i++) 
        {
            if (result[i] == 'a' || result[i] == 'e' || result[i] == 'i' || result[i] == 'o' || result[i] == 'u') vowel++; //모음 체크
            else consonant++; //자음 체크
        }

        if(vowel>=1 && consonant>=2) //최소 한개의 모음과 최소 두개의 자음으로 구성
        {
            for(int i=0; i<result.size(); i++)
            {
                cout << result[i];
            }
            cout << "\n";
        }
    }

    for(int i=cur; i<v.size(); i++)
    {
        result.push_back(v[i]);
        func(size+1, i+1);
        result.pop_back(); //백트래킹
    }
}

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

    cin >> L >> C;
    for(int i=0; i<C; i++)
    {
        char c;
        cin >> c;
        v.push_back(c);
    }
    sort(v.begin(), v.end());
    func(0, 0);
    return 0;
}

백트래킹을 이용한 문제이다.

처음에 문자를 입력받고 해당 문자를 입력받은 벡터의 사이즈만큼 반복문을 돌려서 백트래킹을 해준다.

이때 현재 인덱스의 다음값 뿐만이 아니라, 사이즈도 +1하여 같이 넘겨주는데 해당 사이즈가 주어진 L과 같아지면 자음과 모음에 대한 체크를 시작한다.

 

백트래킹 시에 문자를 또 따로 담아줬던 벡터 result를 기준으로 모음과 자음에 대한 갯수를 체크하고, 문제에서 주어진 조건인 최소 1개의 모음과 최소 2개의 자음으로 구성된 것이 맞다면 해당 벡터에 담겨진 문자들을 출력해준다.