글 읽기 - 돌다리 건너기

ls123kr 6년 전 0

제가 작성한 코드인데 어떤 테스트케이스에서 틀렸을까요?..

RRRRRRRRRR

RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

위 테스트 케이스도 1695321056 으로 잘나옵니다.

또 코드에서 보완했으면 하는 점이 있다면 알려주시면 감사하겠습니다.

#include<cstdio>
#include<cstring>
char word[30];
char s[2][150];
unsigned long long cache[150][2][30];
unsigned long long dp(int p, int q, int r){
	unsigned long long &ret = cache[p][q][r];
	if (!word[r]) return ret=1;
	if (!s[q][p] && p!=-1) return ret=0;
	if (ret!=0) return ret;
	unsigned long long h = 0;
	for (int i = 1; i <= strlen(s[q]) - p; i++){
		if (s[q][p+i] == word[r])
			h += dp(p + i, (q + 1) % 2, r + 1);
	}
	return ret = h;
}
int main(){
	scanf("%s", word);
	for (int i = 0; i < 2; i++)
		scanf("%s", s[i]);
	printf("%lld", dp(-1, 0, 0) + dp(-1, 1, 0));
	return 0;
}