글 읽기 - 2671번 질문입니다.

ehdgur0822 8년 전 0

DFA의 개념을 써서 풀어봤습니다.

계속 틀렸다고 나오는데.

틀린 예시를 못찾겠습니다.

고수분들 부탁드려요.

소스는 다음과 같고

s는 state를 나타내구요 o,1이 스트링에 나오는 문자입니다.

상태표가 아래와 같은데 시작점이 스트링의 처음이 1이면 s0이고 0이면 s1부터 시작되게끔 하였습니다.

마침이 되도 괜찮은 상태는 s3,s4,s5입니다.

이렇게 만들면 걸리는 경우가 101 이런 경우라서

이런 경우를 처리하기 위해 flag를 두어서 처리하였습니다.

s4가 s1으로 갈 때는 문제가 없기에 flag를 지워주었고

s0에서 s1으로 갈때 flag로 표시를 해주었고

s5에서 s0로 갈때 flag를 표시해주었습니다.

안되는 예시를 들어주시면 감사하겠습니다.

	0	1
s0	s1	error
s1	s2	s5
s2	s2	s3
s3	s6	s4
s4	s1	s4
s5	s6	s0
s6	error	s5

#include <stdio.h>
#include <string.h>

int main()
{
	char str[201];
	int find[7][2];
	int state,i;
	int flag;

	find[0][0] = 1;
	find[0][1] = -1;
	find[1][0] = 2;
	find[1][1] = 5;
	find[2][0] = 2;
	find[2][1] = 3;
	find[3][0] = 6;
	find[3][1] = 4;
	find[4][0] = 1;
	find[4][1] = 4;
	find[5][0] = 6;
	find[5][1] = 0;
	find[6][0] = -1;
	find[6][1] = 5;

    scanf("%s",str);
    
    if(str[0] == '0')
	{	
		if(str[1] == '0')
			state = -1;
		else
		{
			flag = 0;
			state = 1;
		}
	}
	else
	{
		flag = 1;
		state = 0;
	}
	if(state != -1)
	{
		for(i=1;i<strlen(str);i++)
		{
			if(state == 0 && str[i]-48 == 0)
			{
				flag=1;
			}
			if(state == 1 && str[i]-48 == 0)
			{
				if(flag == 0)
				{
					state = -1;
					break;
				}
			}
			if(state == 1 && str[i]-48 == 1)
			{
				if(flag == 1)
				{
					state = -1;
					break;
				}
			}
			if(state == 4 && str[i]-48 == 0)
			{
				flag = 2;
			}
			if(state == 5 && str[i]-48 == 1)
			{
				flag = 1;
			}
			state = find[state][str[i]-48];
			if(state == -1)
				break;
		}
	}
    if(state == 3 || state == 4 || state == 5)
		printf("SUBMARINE\n");
	else
		printf("NOISE\n");

	return 0;   
	
}

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

문제

문제

출처

ICPC

2671번 질문입니다.

ehdgur0822 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말