백준 1013번: Contact

[문제 링크]

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

---

재귀 호출을 이해하고 있는지 물어보는 문제였다.

 

(100+1+) 패턴 동작 요약

1. 먼저 "100" 이 정확히 나오는지 확인한다.
2. 그 뒤의 0들을 모두 소비한다. → 100+
3. 그 다음에는 반드시 1이 하나 이상 나와야 한다.
4. 1+ 구간에서는
   • 1을 하나씩 소비할 때마다, 그 시점(idx)부터 나머지 문자열이 다시 (100+1+ | 01)+ 를 만족하는지 재귀적으로 검사한다.
   • 어느 위치에서든 재귀 함수가 true 를 반환하면 전체도 true
5. 1들을 다 소비한 뒤
   • 문자열이 딱 끝났으면 → 성공
   • 그 뒤에 문자가 더 있으면 → 그 위치부터 다시 isContact 를 호출해 이어지는 패턴인지 검사

(01) 패턴 동작 요약

1. "01"이 정확히 나오는지 확인한다.
2. "01"을 소비한 뒤
   
   • 문자열이 끝났을 경우 → 성공
   • 그 뒤에 문자가 더 있으면 → 그 위치부터 다시 isContact 를 호출해 이어지는 패턴인지 검사

4. 종료 조건과 결과

• 재귀 호출이 문자열 끝까지 도달하면서 모든 구간이
  100+1+ 또는 01 패턴으로만 나누어지면 → "YES"
• 중간에 어느 위치에서든 패턴이 깨지면 → "NO"

5. 시간 복잡도

• 문자열 길이가 최대 200이고, 각 인덱스가 유효하게 검사되는 횟수는 제한적이라 최악의 경우 O(N^2) 수준에서 충분히 통과 가능하다.

---

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

bool isContact(const string& str, int curIdx);

bool isContactFirst(const string& str, int curIdx)
{
	int idx = curIdx;

	if (idx + 3 >= str.size())
		return false;

	if (str[idx++] == '1' && str[idx++] == '0' && str[idx++] == '0')
	{

		while (idx < str.size() && str[idx] == '0')
		{
			idx++;
		}

		if (idx >= str.size())
			return false;

		while (idx < str.size() && str[idx] == '1')
		{
			idx++;

			if (idx >= str.size() || isContact(str, idx))
				return true;
		}
	}

	return false;
}

bool isContactSecond(const string& str, int curIdx)
{
	int idx = curIdx;

	if (idx + 1 >= str.size())
		return false;

	if (str[idx++] == '0' && str[idx++] == '1')
	{
		if (idx >= str.size())
			return true;
		else
			return isContact(str, idx);
	}

	return false;
}

bool isContact(const string& str, int curIdx)
{
	return isContactFirst(str, curIdx) || isContactSecond(str, curIdx);
}

int main(void)
{
	int T;
	cin >> T;

	while (T--)
	{
		string str;
		cin >> str;

		if (isContact(str, 0))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}