글 읽기 - 데이터 확인 부탁드립니다!

wwiiiii 6년 전 0

https://www.acmicpc.net/board/... 에 관련된 이슈입니다.

114번째 줄의 assert 문에 걸립니다.

입력되는 문자열에 R, I, N, G, S가 아닌 문자가 들어있는 것 같습니다.

#include <cstdio>
#include <cstring>
#include <cassert>
#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;
    return 0;//assert(false);
}

void input()
{
	scanf("%s", order); //gets(order);
	scanf("%s", devil); //gets(devil);
	scanf("%s", angel); //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()
{
	memset(devilLetter, -1, sizeof(devilLetter));//fill_n(&devilLetter[0][0], 110 * 5, -1);
	memset(angelLetter, -1, sizeof(angelLetter));//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);
    char rings[]="RINGS";
    for(int i=0;i<orderlen;i++)
    {
        bool flag = false;
        for(int j=0;j<5;j++) flag = flag || rings[j] == order[i];
        assert(flag);
    }
	Letterini();
	//debug();
	backtracking(0, orderlen, ANGEL);
	backtracking(0, orderlen, DEVIL);
}

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

int main()
{
	input(); 
	process();
	output();
}

skysign 3년 전 0

RINGS이외으 글자가 들어 있어도, 문제 푸는 것은 가능할 것 같습니다.

문제 풀이 영상 참고하세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

데이터 확인 부탁드립니다!

wwiiiii 6년 전 0

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말