C++:: boj 1013 < Contact >

문제를 이해하기도 조금 어려웠던 문제이고, 규칙을 찾기가 조금 까다로웠던 문제이다.

문제의 핵심은 항상 언제든 올수 있는 문자열의 종류는 "100" 과 "01" 이고
"100" 다음에는 무조건 "0" "1" 이 나와한다는 점이다. 이때 "1"이 나오게 된다면 "1" "100" "01" 중 에서 선택하여 골라야 하고 "0" 을 고르면 다시 "0" 또는 "1" 이 나오게 된다. 이와 같은 방식으로 연관관계가 정리가 된다.

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

string res = "NO";// 결과 출력값

void dfs(string tmp, string& answer, int size, string choosed) {
	if (res == "YES" || size > answer.size() || answer.substr(0, size) != tmp) {
		return ;// 이미 결과를 찾았거나, 사이즈가 넘어갔거나, 문자열이 달라졌다면
	}
	if (tmp == answer && choosed != "100") {// 문자열의 끝이 100 일수는 없다.
		res = "YES";
		return ;
	}
	if (choosed == "") {
		dfs(tmp+"01", answer, size+2, "");
		dfs(tmp+"100", answer, size+3, "100");
	} else if (choosed == "100") {
		dfs(tmp+"1", answer, size+1, "1");
		dfs(tmp+"0", answer, size+1, "100");
	} else if (choosed == "1") {
		dfs(tmp+"1", answer, size+1, "1");
		dfs(tmp+"01", answer, size+2, "");
		dfs(tmp+"100", answer, size+3, "100");
	}
}

int main() {
	int t;
	cin >> t;
	string input, answer;

	while (t--) {
		cin >> input;
		dfs("", input, 0, "");
		cout << res << "\n";
		res = "NO";
	}
}