[백준] 1759 - 암호만들기

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

1759번: 암호 만들기

 일전에 풀었던 N-Queen 문제와 비슷한 백트래킹을 이용한 문제이다. (N-Queen 문제가 순수 백트래킹 알고리즘만을 이용하는 것이므로 백트래킹에 대해서 좀더 높은 이해를 원한다면 이전글을 참고할 것.)

[Dev/Algorithm] - [백준] 9663 - N-Queen

[백준] 9663 - N-Queen

 이번 문제는 백트래킹 이외에도 몇가지 주의해야할 사항이 있는데..

1. 최소 한개의 자음과 최소 두개의 자음으로 구성되어야 하는 조건
   - 재귀 호출을 하면서, 자음과 모음의 구성을 확인하고 조건 검색을 해야한다.
2. 정렬된 문자열을 선호하는 조교들의 성향
   - 꽤 이해할수 없는 취향이긴 하지만, 백트레킹 알고리즘을 돌리기 전에 입력받은 문자들을 정렬해주면 된다.

 생각보다는 쉽게 풀렸다.

#include <iostream>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int L, C;
char input[16];
char password[16];
bool moum[27];

int cmp(const void * a, const void * b)
{
    return ( *(char*)a - * (char*)b );
}

void solve(int pw_count, int start_idx, int pw_point, string str){
  if(pw_count == L){
    if(pw_point >=2 && pw_point <= L-1){
      printf("%s\n", str.c_str());
    }
    return;
  } 
  if(start_idx == C){
    return;
  }
  string add_str = str + input[start_idx];
  solve(pw_count+1, start_idx+1, pw_point-(moum[input[start_idx]-'a']?1:0), add_str);
  solve(pw_count, start_idx+1, pw_point, str);

}

int main(){
  scanf("%d%d", &L, &C);
  memset(password, '\0', sizeof(password));
  memset(input, '\0', sizeof(input));
  memset(moum, false, sizeof(moum));
  moum['a'-'a'] = true;
  moum['e'-'a'] = true;
  moum['i'-'a'] = true;
  moum['o'-'a'] = true;
  moum['u'-'a'] = true;

  for(int i=0; i<C; ++i){
    char temp[2];
    scanf("%s", temp);
    input[i] = temp[0];
  }

  qsort(&(input[0]), C, sizeof(char), cmp);

  solve(0, 0, L, "");

  return 0;
}