[BOJ]2602 : 돌다리 건너기(c++)

[문제] : https://www.acmicpc.net/problem/2602

[풀이]

재귀 함수로 두루마리에서의 현재 위치, 돌다리에서의 현재 위치, 돌다리의 유형을 매개변수로 전달받아 반대쪽의 돌다리를 현재 위치 + 1 부터 반복문을 통해 탐색하여 다음 가야할 문자와 같다면 재귀함수로 보내 리턴되는 값을 변수에 더하였다. 만약 두루마리에서의 현재 위치가 마지막 위치라면 1을 리턴되게 하였다.

[코드]

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

string s;
string a, b;
int cache[21][101][2];

int DP(int here, int idx, int flag)
{
	if (here == s.size()-1)
	{
		return 1;
	}

	int& ret = cache[here][idx][flag];
	if (ret != -1)
	{
		return ret;
	}

	int res = 0;
	if (flag == 0)
	{
		for (int i = idx + 1; i < b.size(); ++i)
		{
			if (b[i] == s[here + 1])
			{
				res += DP(here + 1, i, flag + 1);
			}
		}
	}
	else
	{
		for (int i = idx + 1; i < a.size(); ++i)
		{
			if (a[i] == s[here + 1])
			{
				res += DP(here + 1, i, flag - 1);
			}
		}
	}

	return ret = res;
}

int main(void)
{
	cin >> s >> a >> b;
	memset(cache, -1, sizeof cache);

	int cnt = 0;
	for (int i = 0; i < a.size(); ++i)
	{
		if (s[0] == a[i])
		{
			cnt += DP(0, i, 0);
		}

		if (s[0] == b[i])
		{
			cnt += DP(0, i, 1);
		}
	}

	cout << cnt << endl;
}