[백준/C++] 1013. Contact

문제

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

1013번: Contact

문제가 굉장히 길고 복잡하다.. 꼼꼼히 읽어보면서 이해하는 시간이 필요하다. 

요약하자면, 결과적으로 입력받은 문자열이 (100+1+|01)+ 패턴에 해당하는지 아닌지를 판단하면 되는 문제이다.

풀이

(100+1+|01)+를 쪼개서 보자. 

100+1+ = A, 01 = B라고 하면,

(A|B)+ 이므로, A나 B가 계속 반복적으로 나타나면 된다. 

B는 01 자체이고, 

A 는 100+1+이다. A를 더 뜯어보면, 

10 0(0...) 1(1...) 이런식이기 때문에 1001부터 ...자리에 0이나 1이 몇개든 더 들어가도 되는 구조이다. 

 

복잡한 알고리즘은 생각이 안나서, 그냥 문자열 맨 앞에서부터 패턴으로 if/else로 나눠서 재귀를 돌리는 방식으로 구현했다. 

먼저 맨 앞이 1이라면

100+1+인지 확인해야 한다. 즉 1나오고 적어도 0이 2개, 적어도 1이 1개 나오는지 확인해본다. 

그리고, 1이 1개 이상일 경우 마지막 1뒤에 나오는 0의 개수를 추가로 확인해서 

0이 1개면 : 마지막1까지 버리고 남은 문자열로 반복한다. (다음 패턴이 01이기 때문에)

ex) 100101... -> 01... , 1000111101... -> 01... 

0이 2개 이상이면 : 마지막 1을 남긴 문자열로 반복한다 (다음 패턴도 100+1+이기 때문에)

ex ) 10011000... -> 1000... , 1001111110001... -> 10001...

 

맨 앞이 0이라면,

01을 자르고 남은 문자열로 반복한다. 

 

이렇게 재귀를 돌다가, 조건에 맞지 않는 경우가 나오면 패턴을 만족하지 않는것으로 판단하면된다. 

코드를 보는게 더 이해가 쉬울 것 같다..!

코드

#include <iostream>
#include <string>

#define endl '\n'

using namespace std;

bool recursive(string s) {
	bool flag = false;
	int size = s.size();
	if (size == 0) return true;
	if (s[0] == '0') 
		if (s[1] == '1') flag |= recursive(s.substr(2)); // 01자르고 반복
	else { // s[0] == '1'
		// 0 구간
		int i = 1;
		while (i < size && s[i] == '0') {
			i++;
		}
		if (i <= 2) {
			return flag;
		}
		// 1 구간 
		int j = i;
		while (j < size && s[j] == '1') {
			j++;
		}
		// 1이 1개
		if (j == i + 1)
			flag |= recursive(s.substr(j));
		// 1이 2개 이상일 때 마지막 1 뒤에 0 개수 확인
		if (j >= i + 2) {
			if (j == size - 1) return flag;
			if (j + 1 < size && s[j + 1] == '0') 
				flag |= recursive(s.substr(j-1));
			else 
				flag |= recursive(s.substr(j));
		}
	}
	return flag;
}
int main() {
	int N; cin >> N;
	for (int n = 0;n < N;n++) {
		string input; cin >> input;
		string answer = (recursive(input)) ? "YES" : "NO";
		cout << answer << endl;
	}
	return 0;
}

결과