[C++] 1013 - Contact

문제링크 : https://www.acmicpc.net/problem/1013

1013번: Contact

 

잠수함 식별이라는 문제와 똑같은 문제다.

 

잠수함 식별문제를 풀 때는 문자열 처리를 통해서 풀었지만 질문 중에서 다음과 같은 글을 보게 됐다.

www.acmicpc.net/board/view/1312

글 읽기 - 1013 Contact 질문입니다. *솔루션 스포일러 주의

그래서.. 이 글을 읽고 띠용 해서 북마크만 해놨는데 이제서야 한번 제대로 구현을 해본다.

 

 

위의 글에 있는 내용을 쭉 읽고나서 답변해주신 분의 말씀대로 그림으로 그래프(?)를 노트에 끄적거리면서 여러 시행착오를 겪다가 결국 풀었다. 근데 생각보다 그렇게 복잡하지는 않더라. (응용을 어떻게 할 수 있는지가 문제긴 한데)

 

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

int D[2][8]={
	{1, -1, 5, 2, 1, 5, 5, 6},
	{7, 0, 0, 3, 3, 4, -1, -1}
};

int main(void)
{
	int t;
	int n;
	string tmp;
	cin >> t;

	while(t--)
	{
		n = 0;
		cin >> tmp;

		for(int i = 0; i < tmp.length() && n != -1; ++i)
			n = D[tmp[i]-'0'][n];
		
		if(n == 0 || n == 4 || n == 3)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}