https://www.acmicpc.net/problem/1759
1759번: 암호 만들기
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
www.acmicpc.net
이 문제는 일단 백준상에서 골드 5로 되어있는 문제다 근데 이문제를 보았을 때 느낀게 과연 내가 이 문제가 백트래킹인걸 모르고 풀었을 때 빠르게 정답을 유추 할 수 있었을까? 절대 아니다. 요즘 해당 알고리즘이 주어질 경우에는 그 알고리즘으로 문제를 빠르게 풀지만 내가 어떤 문젠지를 모르면 풀 수 있을 지는 모르겠다. 확실히 실무를 보다보니 머릿속에 생각한 것을 그대로 구현하는 구현능력은 조금 올라갔는데 앞으로도 계속 좋은 일이 있었으면 좋겠
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
char arr[16];
char answer[16];
int cnta;
int cntj;
bool isPassword;
int solution(int level, int beforeindex) {
if (level == N) {
cnta = 0;
cntj = 0;
isPassword = false;
for (int i = 0; i < N; i++) {
if (answer[i] == 'a' || answer[i] == 'e' || answer[i] == 'i' || answer[i] == 'o' || answer[i] == 'u')
{
cnta++;
}
else
cntj++;
if (cnta > 0 && cntj > 1) {
isPassword = true;
break;
}
}
if (isPassword) {
for (int i = 0; i < N; i++) {
cout << answer[i];
}
cout << endl;
}
}
else {
for (int i = beforeindex + 1; i <= M; i++) {
answer[level] = arr[i];
solution(level + 1, i);
}
}
return 0;
}
int main() {
cin >> N >> M;
for (int i = 1; i <= M; i++) {
cin >> arr[i];
}
sort(arr+1,arr+M+1);
solution(0, 0);
}이코드의 경우 모음의 개수를 세주는 CNTA 자음의 개수를 세주는 CNTJ라는 변수가 존재 한다 이 변수의 경우 루프를 돌다가 특정 조건을 만족했을 때 바로 루프를 탈출하게 해준다. 즉 최종 4글자 가 모였을 때 이 문자열이 모음이 1개이상 자음이 2개이상이면 더이상 조건을 판단할 필요없으니 루프를 탈출하게 해주는 것이다.
else {
for (int i = beforeindex + 1; i <= M; i++) {
answer[level] = arr[i];
solution(level + 1, i);
}
}
이 부분의 경우는 재귀를 이용해서 백트래킹을 하기 위함인데 정렬되어있는 arr값에서 자기 이전의 index보다 큰 인덱스 부터 시작하기에 무조건 오름차순이 된다.