Contact

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

1013번: Contact

 

문제 자체가 오토마타를 타겟으로 만든 문제같다.

여러 생각을 해봤지만 진짜 오토마타처럼 순서도를 작성해서 풀어봤다.

중간에 특정 조건이 존재하므로 잘 예외처리를 해야한다.

1. 10011001 (O)

2. 1001001   (X)
3. 100101    (O)

typedef struct{
	int next_state[2];
}state;

state OM[7];

void makeSTATE(int index, int arr_index,int value)
{
	OM[index].next_state[arr_index] = value;
}
void makeOM()
{
	memset(OM, 0, sizeof(OM));
	makeSTATE(0, 0, 1);
	makeSTATE(0, 1, 2);
	makeSTATE(1, 0, -1);
	makeSTATE(1, 1, 0);
	makeSTATE(2, 0, 3);
	makeSTATE(2, 1, -1);
	makeSTATE(3, 0, 4);
	makeSTATE(3, 1, -1);
	makeSTATE(4, 0, -1);
	makeSTATE(4, 1, 0);
}
bool moveOM(char* N, int index)
{
	int length = strlen(N);
	int current_state = 0;
	while (index < length)
	{
		int _n = N[index]-48;
		int next_state = OM[current_state].next_state[_n];

		if (current_state == 1 && next_state == -1)
		{
			if (index >= 3 && N[index - 2] - 48 == 1 && N[index - 3] - 48 == 1)
				current_state = 3;
			else
				break;
		}
		else if (next_state == -1)
			break;
		else
		{
			if (current_state == 3)
			{
				int t_index;
				for (t_index = index; N[t_index] != '\0' && N[t_index] - 48 == 0; t_index++)
					;
				index = t_index;
			}
			else if (current_state == 4)
			{
				int t_index;
				for (t_index = index; N[t_index] != '\0' && N[t_index] - 48 == 1; t_index++)
					;
				index = t_index;
			}
			else
				++index;

			current_state = next_state;
		}
	}

	if (index == length && current_state == 0)
		return true;
	else
		return false;
}
int main()
{
	makeOM();
	int T;
	for (scanf("%d", &T); T > 0; T--)
	{
		char N[255];
		scanf("%s", &N);
		printf("%s\n", (moveOM(N, 0)) ? "YES" : "NO");
	}
}