암호 만들기 / 1759번 백준

문제 

문제 난이도 : 골드 5

문제 분류 : 백 트래킹, 조합, 시뮬레이션, 구현

 

문제 풀이

굉장히 기네요.. 똑똑한 여러분은 좀 더 짧게 쓸 수 있을 거라고 생각합니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int L, C;
vector<char> Words;
vector<bool> Selected(16, false);
vector<char> SelectedWords;

bool IsPromising()
{
    if (SelectedWords.size() == 1)
    {
        return true;
    }

    char Before = NULL;
    int A = 0;
    int B = 0;
    // 모음 자음 카운팅
    if (SelectedWords[0] == 'a' || SelectedWords[0] == 'e' || SelectedWords[0] == 'i'
        || SelectedWords[0] == 'o' || SelectedWords[0] == 'u')
    {
        A++;
    }
    else
    {
        B++;
    }
    for (int i = 1; i <  SelectedWords.size(); i++)
    {
        // 모음 자음 카운팅
        if (SelectedWords[i] == 'a' || SelectedWords[i] == 'e' || SelectedWords[i] == 'i'
            || SelectedWords[i] == 'o' || SelectedWords[i] == 'u')
        {
            A++;
        }
        else
        {
            B++;
        }
        // Promise한지 판별
        if (int(SelectedWords[i - 1]) <= int(SelectedWords[i]))
        {
            continue;
        }
        else
        {
            
            return false;
        }
    }

    // 모음 자운 판별
    if (SelectedWords.size() == L)
    {
        if (A < 1 || B < 2)
        {
            return false;
        }
    }

    return true;
}



void Simulate()
{
    
    if (SelectedWords.size() == L)
    {
        vector<char> s;
        for (int i = 0; i < Words.size(); ++i)
        {
            if (Selected[i] == true)
            {
                s.push_back(Words[i]);
            }
        }

        if (s.size() == L)
        {
            for (char c : s)
            {
                cout << c;
            }
            cout << "\n";
        }

        return;
    }
    else
    {
        for (int i = 0; i < Words.size(); ++i)
        {
            if (Selected[i] == true) continue;
            Selected[i] = true;
            SelectedWords.push_back(Words[i]);
            if (IsPromising())
            {
                Simulate();
            }
            Selected[i] = false;
            SelectedWords.pop_back();
        }
    }


}

int main()
{
    //Input
    cin >> L >> C;
    for (int i = 0; i < C; ++i)
    {
        char word;
        cin >> word;
        Words.push_back(word);

    }
    sort(Words.begin(), Words.end());
    //Find Answer by Backtracking
    Simulate();
}