문제

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

---

풀이

아래의 조건이 백트래킹에 쓰인다는 걸 파악하지 못하면,, 헤매기 쉬운 문제이다.

• 자음이 3번 연속되는 경우
• 모음이 3번 연속되는 경우
• L이 포함되지 않는 경우

필자도 처음에 이 문제를 풀 때 백트래킹을 떠올리지 못하고, 그리디하게 L이 포함되는 경우와 안 되는 경우로 먼저 나누고 이 둘에 대해 경우의 수를 따로 구하려고 했다.

그런데 풀이가 너무 복잡해져서 결국 답을 확인했더니, 백트래킹으로 불가능한 단어를 배제시켜나가면서 최종적으로 3개의 조건을 모두 만족시키는 즐거운 단어 개수를 구하면 되는 것이었다.

다시 말해, 모음(M), L이 아닌 자음(J), L 이렇게 3가지 종류의 문자로 만들 수 있는 단어를 DFS로 구하다가, 즐거운 단어 조건에 벗어난 경우에는 백트래킹 하면 된다.

밑줄의 개수는 최대 10개이기 때문에 3가지 종류의 문자로 만들 수 있는 전체 경우의 수는 3^10이고, 이 중에서 조건에 벗어난 단어는 제외시킨다.

앞으로도 모든 경우의 수를 구하면서 특정한 경우의 수는 배제시켜야 하는 문제를 풀 때, 반드시 백트래킹을 떠올려보자!!

그리고 정답은 2^63 - 1 을 넘지 않는다고 했으므로 long long형으로 출력해야 한다.

C++ 코드

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

string input;
vector<int> vowels = {'A', 'E', 'I', 'O', 'U'};

bool isVowel(char ch){
	return find(vowels.begin(), vowels.end(), ch) != vowels.end();
}

ll dfs(ll idx, ll ja, ll mo, bool containL){
	if(ja >= 3 || mo >= 3) return 0;
	if(idx == input.size()) return containL; // 0 또는 1 

	ll ans = 0;
	if(input[idx] == '_'){
		// L이 아닌 자음
		ans += dfs(idx + 1, ja + 1, 0, containL) * 20; 

		// 자음 L
		ans += dfs(idx + 1, ja + 1, 0, true);

		// 모음
		ans += dfs(idx + 1, 0, mo + 1, containL) * 5; 
	}else{
		if(isVowel(input[idx])){
			ans += dfs(idx + 1, 0, mo + 1, containL);
		}else{
			if(input[idx] == 'L'){
				ans += dfs(idx + 1, ja + 1, 0, true);
			}else{
				ans += dfs(idx + 1, ja + 1, 0, containL);
			}
		}
	}

	return ans;
}

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

	cin >> input;

	cout << dfs(0, 0, 0, false);
	
	return 0;
}