[백준/구현/백트래킹/C++] 1759번 암호 만들기

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

문제 해결 방법

1. 입력받은 문자들을 정렬한다

2. 이전 인덱스를 저장해서 다음 인덱스를 고를수 있게한다

3. 자음의 수와 모음의 수 저장한다

자음과 모음의 구별은

위 사진처럼 생각해서 아래 코드처럼 구현했다. 모음인 경우 m+1, 자음인 경우 j+1

int diff = alpha[i]-'a';
if(diff==0 || diff==4 || diff==8 || diff==14 || diff==20) // 모음인 경우
    makeCode(k+1, m+1, j, i);
else // 자음인 경우
    makeCode(k+1, m, j+1, i);

 

4. 암호가 n자리 만들어졌을 때 모음이 1개 이상이고 자음이 2개 이상인 경우에만 출력

if(k==n){
    if(m>=1 && j>=2){ // 모음 1개 이상, 자음 2개 이상인 경우
        for(int i=0; i<n; i++)
            cout << arr[i];
        cout << '\n';
    }
    return;
}

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n, c;
vector<char> alpha;
bool isused[16];
char arr[16];

void makeCode(int k, int m, int j, int index){ // 문자 총 개수, 모음 개수, 자음 개수, 이전 인덱스
    if(k==n){
        if(m>=1 && j>=2){ // 모음 1개 이상, 자음 2개 이상인 경우
            for(int i=0; i<n; i++)
                cout << arr[i];
            cout << '\n';
        }
        return;
    }

    for(int i=index+1; i<c; i++){ // 다음 인덱스부터 탐색
        if(!isused[i]){
            isused[i] = true;
            arr[k] = alpha[i];

            int diff = alpha[i]-'a';
            if(diff==0 || diff==4 || diff==8 || diff==14 || diff==20) // 모음인 경우
                makeCode(k+1, m+1, j, i);
            else // 자음인 경우
                makeCode(k+1, m, j+1, i);

            isused[i] = false;
        }
    }

}

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

    cin >> n >> c;
    for(int i=0; i<c; i++){
        char x;
        cin >> x;
        alpha.push_back(x);
    }
    sort(alpha.begin(), alpha.end());

    makeCode(0, 0, 0, -1);

    return 0;
}