백준 1759 암호만들기

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

1759번: 암호 만들기

문제를 보면 사전순으로 가능성 있는 암호를 모두 출력하는 문제 입니다. 가장 큰 실수는 입력과 출력만 보고 

사전순으로 나오게 백트래킹을 돌리면 되는 문제라고 생각했습니다.

 

풀이방식은  입력으로 주어진 배열을 sort함수를 이용하여 오름차순으로 정렬을 합니다.

예제가

a t c i s w 이것을 정렬을 하게되면

a c i s t w 이렇게 되고

그렇게해서

 주어진 L으로 입력이 들어온 정수만큼 사전 순으로 뽑는 방식입니다.

#include<stdio.h>
#include<algorithm>
using namespace std;
int L, C;
char passWord[15];
char answer[15];
int chk[15];
int idx1 = 0;
void dfs(int idx) {
    if (idx1 == L) {
        int cnt0 = 0;
        int cnt1 = 0;
        for (int i = 0; i < L; i++) {
            if (answer[i] == 'a' || answer[i] == 'e' || answer[i] == 'i' || answer[i] == 'o' || answer[i] == 'u')cnt0++;
            else {
                cnt1++;
            }
        }
        if (cnt0 >= 1 && cnt1 >= 2)
        {
            printf("%s", answer);
            printf("\n");
        }
        return;
    }
    for (int i = idx; i < C; i++) {
            answer[idx1++] = passWord[i];
            dfs(i + 1);
            answer[idx1--] = 0;
    }
}
int main(void) {
    scanf("%d %d", &L, &C);
    for (int i = 0; i < C; i++) {
        scanf(" %c", &passWord[i]);
    }
 
    sort(passWord, passWord + C);
 
    dfs(0);
    return 0;
}

 

 방식은 기본 백트래킹으로 돌리면서 다른배열에 L개가 되도록 저장을 하는것이 포인트이고 

L개를 만족하게 된다면 출력하는 풀이입니다.

 

저는 여기서 실수를 했는데 문제 지문에 

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다.

이렇게 명시되어있는것을 무시해서 cstw가 나오는것이였습니다.

cstw는 모음이 한개도 존재하지 않아 암호로 되면 안되는것으로

이를 해결하기위해 

위와같이 모음이 몇개인지 자음이 몇개인지 암호가 될수 있는 조건을 세고 그 조건을 만족한경우

출력이 되는 형식으로 문제를 해결했습니다.

 

백트래킹을 알고 있는 분이라면 누구든 쉽게 풀수 있는 문제였고 다시 실수를 하지 않도록 주의를 기울여 문제를

풀도록 해야겠습니다.

 

오늘은 여기까지 입니다. 감사합니다.