글 읽기 - 2602 돌다리 건너기 문제 어떤 경우를 빼먹었는지 모르겠습니다 ㅜㅜ

wwiiiii 9년 전 0

원래는 다음 알파벳을 찾는 과정을 그냥 문자열을 선형탐색하며 위치를 찾았는데, 그렇게 했더니 마지막 테스트 케이스에서 시간 초과가 되서 어떤 위치 index 이후의 어떤 알파벳이 존재하는 위치를 바로 반환해주는 배열을 잡았는데, 갑자기 틀렸다고 나옵니다 ㅜㅡ

#include <cstdio>
#include <cstring>
#include <algorithm>
#define DEVIL false
#define ANGEL true
using namespace std;
char order[30];
char devil[110];
char angel[110];
//letter[index] : index포함해서 index보다 뒤에서 R이 처음 나오는 위치 반환
//값이 -1이면 존재하지 않음
int devilLetter[110][5];//0은 R 1은 I 2는 N 3은 G 4는 S
int angelLetter[110][5];//0은 R 1은 I 2는 N 3은 G 4는 S

int ans, angellen, devillen, orderlen; 

int convert(char a)
{
	if (a == 'R') return 0;
	if (a == 'I') return 1;
	if (a == 'N') return 2;
	if (a == 'G') return 3;
	if (a == 'S') return 4;
    else return 5;
}

void input()
{
	gets(order);
	gets(devil);
	gets(angel);
}

//now는 탐색시작 위치 leftnum은 남은 돌다리 칸수(order) bool은 찾아야할게 
//devil에 있는지 angel에 있는지, 매크로로지정
void backtracking(int now, int leftnum, bool place)
{
	int  temp, chase;
	if (leftnum == 0) { ans++; return; }
	char target = order[orderlen - leftnum];
	//printf("search from %d, target is %c, at %s, left %d\n", now, target, place ? "ANGEL" : "DEVIL", leftnum);
	if (place == DEVIL)
	{
		if (now >= devillen) return;
		chase = devilLetter[now][convert(target)];
		while (chase != -1)
		{
			backtracking(chase + 1, leftnum - 1, !place);
			chase = devilLetter[chase + 1][convert(target)];
		}
		return;
	}
	else
	{
		if (now >= angellen) return;
		chase = angelLetter[now][convert(target)];
		while (chase != -1)
		{
			backtracking(chase + 1, leftnum - 1, !place);
			chase = angelLetter[chase + 1][convert(target)];
		}
		return;
	}
	return;
}

void Letterini()
{
	fill_n(&devilLetter[0][0], 110 * 5, -1);
	fill_n(&angelLetter[0][0], 110 * 5, -1);
	int R = -1, I = -1, N = -1, G = -1, S = -1;
	for (int i = devillen - 1; i >= 0; i--)
	{
		if (devil[i] == 'R') R = i;
		else if (devil[i] == 'I') I = i;
		else if (devil[i] == 'N') N = i;
		else if (devil[i] == 'G') G = i;
		else if (devil[i] == 'S') S = i;
		devilLetter[i][0] = R;
		devilLetter[i][1] = I;
		devilLetter[i][2] = N;
		devilLetter[i][3] = G;
		devilLetter[i][4] = S;
	}
	R = -1, I = -1, N = -1, G = -1, S = -1;
	for (int i = angellen - 1; i >= 0; i--)
	{
		if (angel[i] == 'R') R = i;
		else if (angel[i] == 'I') I = i;
		else if (angel[i] == 'N') N = i;
		else if (angel[i] == 'G') G = i;
		else if (angel[i] == 'S') S = i;
		angelLetter[i][0] = R;
		angelLetter[i][1] = I;
		angelLetter[i][2] = N;
		angelLetter[i][3] = G;
		angelLetter[i][4] = S;
	}
}

void process()
{
	int temp;
	devillen = strlen(devil);
	angellen = strlen(angel);
	orderlen = strlen(order);
	Letterini();
	backtracking(0, orderlen, ANGEL);
	backtracking(0, orderlen, DEVIL);
}

void output()
{
	printf("%d", ans);
}

int main()
{
	//freopen("input.txt", "rt", stdin);
	input(); 
	process();
	output();
}