글 읽기 - CONTACT 상태천이도 질문

p_ce1052 4년 전 0

다음과 같이 상태천이도를 그려서 냈더니 틀렸습니다를 받았습니다. 모든 경우를 고려한 것 같은데 어디가 문제일까요?

#include<iostream>
#include<vector>
#include<string>
using namespace std;
string s;

bool automata(int curr,int start){
	if(start==s.length()){
		if(curr == 1 || curr == 7) return true;
		return false;
	}
	if(s[start]=='0'){ //0인 경우 
		if(curr==1) return automata(2,start+1);
		if(curr==2) return automata(4,start+1);
		if(curr==3) return automata(5,start+1);
		if(curr==4) return false;
		if(curr==5) return automata(6,start+1);
		if(curr==6) return automata(6,start+1);
		if(curr==7) return automata(4,start+1);
	}
	else{
		if(curr==1) return automata(3,start+1);
		if(curr==2) return automata(1,start+1);
		if(curr==3) return automata(4,start+1);
		if(curr==4) return false;
		if(curr==5) return automata(4,start+1);
		if(curr==6) return automata(7,start+1);
		if(curr==7) return (automata(7,start+1) || automata(1,start+1));
	}
}

int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>s;
		if(automata(1,0)) cout<<"YES"<<'\n';
		else cout<<"NO"<<'\n';
	}
}

djm03178 4년 전 1

DFA를 만드신 거라면 28번째 줄처럼 같은 입력에 대해 두 군데를 가보는 일이 있어서는 안 됩니다.

p_ce1052 4년 전 0

DFA에 대해서는 잘 모르지만 위 경우에 7번 정점에 있을 때 문자가 1이라면 그대로 남아있어도 되고 1번으로 가도 둘 중 어느 경우만 맞으면 답이라고 생각해서 저렇게 하였습니다. 7번 정점이 (100+1+)패턴의 1+ 를 처리할 때인데 뒤에 1을 붙여서 앞의 패턴을 안끝내도 되고 끝내고 새로운 패턴을 시작할 수도 있어서 저렇게 해도 맞지 않나요?

djm03178 4년 전 1

반례는 100101입니다. YES가 나와야 합니다.

bupjae 4년 전 2

7번 노드가 잘못되었습니다.

7번 노드에서 새로운 100+1+ 패턴이 시작되려는 걸 살펴보려면, 1 한 개를 읽은 후에 1번 노드가 아니라 3번 노드로 가야 합니다.

입력:
1
10011001

정답:
YES

오답:
NO

p_ce1052 4년 전 0

저 그림이 잘못되었군요 감사드립니다

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

문제

문제

출처

ICPC

CONTACT 상태천이도 질문

p_ce1052 4년 전 0

djm03178 4년 전 1

p_ce1052 4년 전 0

djm03178 4년 전 1

bupjae 4년 전 2

p_ce1052 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말