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

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

1759번: 암호 만들기

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

주어진 알파벳을 통해 암호를 만드는 문제입니다.

암호가 되는 조건은 모음이 1개 이상, 자음이 2개 이상입니다.

나올 수 있는 모든 경우를 출력하는 것이기에 백트래킹을 사용하면 됩니다.

 

또한, 출력은 사전 순이기에 백트래킹을 시작하기 전에, 오름차순 정렬을 해주고 시작하면 편하게 코드를 짤 수 있습니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>

using namespace std;

int N, M;
char Alpabet[16];
int check[16];
vector<char> Select;

void select_alpha(int start, int now, int cnt){
    if(now == cnt){
        int C = 0, V = 0;
        for(int i = 0; i < Select.size(); i++){
            if(Select[i] == 'a' || Select[i] == 'e' || Select[i] == 'i' || Select[i] == 'o' || Select[i] == 'u'){
                V++;
            }
            else C++;
        }
        if(V >= 1 && C >= 2){
            for(int i = 0; i < Select.size(); i++) cout << Select[i];
            cout << "\n";
        }
    }
    else{
        for(int i = start; i <= M; i++){
            if(check[i] != 0) continue;
            Select.push_back(Alpabet[i]);
            check[i] = 1;
            select_alpha(i, now+1, cnt);
            check[i] = 0;
            Select.pop_back();
        }
    }
}

void solve() {
    sort(Alpabet+1, Alpabet+M+1);
    for(int i = 1; i <= M; i++){
        Select.push_back(Alpabet[i]);
        check[i] = 1;
        select_alpha(i, 1, N);
        check[i] = 0;
        Select.pop_back();
    }
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
	    cin >> Alpabet[i];
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요