[백준 / #1759 / C++] 암호 만들기

이 문제는 필자가 좋아하는 문제 유형이다. 백트래킹을 연습하기 좋은 문제 같다.

 

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

1759번: 암호 만들기

 

 

문제 해석:

 

 

 이 문제는 만들 수 있는 모든 암호를 출력해주는 문제이다. 정수 L은 만들어야 하는 암호의 길이이고, 정수 C는 주어지는

 

알파벳의 수이다. 두 정수 모두 최대 크기는 15이다. 암호는 반드시 모음을 하나 이상 포함하고 자음을 두개 이상 포함해야

 

한다. 그 말인 즉, 모음을 하나 이상 포함하고 자음을 두개 이상 포함할 때 완성된 암호를 출력 해주면 된다. 이는 곧 백트래

 

킹(Backtracking)에 해당하며 만약 암호의 길이가 완성되었는데 위 조건을 만족하지 않는다면 한 과정 뒤로 가서 다음 단어를 accept 해주

 

는 형식을 취할 수 있을 것이다.

 

 

 

알고리즘 해설 및 코드:

 

 

 

 

문제에서 요구한 암호는 사전 순이므로 입력받은 문자들을 algorithm 헤더 파일에 속한 sort를 이용해 정렬해준다. 여기서

 

배열의 sort()는 sort(배열, 배열 + size);를 사용하면 되고, vector의 경우 vector(v.begin(), v.end());를 사용하면 된다.

 

 

 우선 모음인지 아닌지 판단해주는 함수인 find_vowel을 짜줬다. 만약 모음이면 true를, 아니면 false를 반환해준다. 여기서

 

2가지 선택지가 존재하는데 필자는 모음인지만 판단해주는 함수를 통해 코드를 짰는데 find_vowel 함수를 모음과 자음의

 

개수를 세어주는 함수로 만든다면 코드가 더욱 간결하게 나올 것이다.

 

 

 이제 백트래킹을 활용하여 암호의 모든 경우의 수를 구해주는데 만약 현재 ind(index)가 가르키는 단어가 모음이면 vowel

 

을 +1 해주어 재귀를 호출한다. 만약 자음이면 마찬가지로 consonant를 +1 해주어 재귀를 호출하고 각각의 경우에 대해 현

 

재 구하고 있던 암호에 +하여 덧붙여 재귀를 호출한다. 또한 현재의 단어를 구하는 암호에 accept 하지 않는 경우도 있으므

 

로 아무것도 +하지 않고 ind(index)만 +1 해주어 재귀를 마지막에 호출해준다. 이 때, 범위에 조금 신경을 쓸 필요가 있다.

 

만약 남은 암호의 길이가 3인데 사용할 수 있는 단어가 2개 남았다면 그 뒤의 계산은 무의미할 것이다. 따라서 범위를 설정

 

해줌에 따라 불필요한 연산을 줄여 실행시간을 개선시킨다. 이렇게 문제를 해결할 수 있다.

 

 

 

 범위를 제한하고, 모음에 대한 처리를 어떻게 할 지만 생각한다면 금방 풀 수 있을 것이다.