문제 출처

1. 문제설명

• 종이가 어떻게 접혀있는지 문자열로 주어진다.
  • 1은 바깥으로, 0은 안쪽으로 접힌 것이다.
• 문자열의 길이는 항상 $2^n-1$ 이다.
  • 즉, 홀수

2. 알고리즘 설계

• 문자열의 길이가 $2^n-1$인 이유는
  • 짝수면 무조건 성립되지 않기 때문이다.
• 한 면이 OUT이면 반대면은 반드시 IN이어야 한다.

3. 로직

• 길이가 홀수이므로, 중심을 정할 수 있다.
• 중심을 기준으로 좌/우가 서로 반대인지 확인
  • 2개의 변수를 이용해 왼쪽은 ++, 오른쪽은 --를 하면서 탐색
  • 같아지는 지점이 있으면 false
• 시작점이 중심점보다 같거나 커질 때까지 상기 과정 반복
• 예시
  • in : 1000110
    • 1번째 재귀
      • center : 3번째 index의 0
      • 0번째 n-1번째를 각각 start, end로 설정
      • 각 index의 값은 서로 반대
    • 2번째 재귀
      • center : 1번째 index의 0
      • 0번째 2번째를 각각 start, end로 지정
      • 각 index의 값은 서로 반대
    • 3번째 재귀
      • start>=end가 되어 종료
  • 2번째 재귀에서 중심의 왼쪽만 분할정복하는 이유
    • 왼쪽이 제대로 되었다면, 반대쪽은 완전히 반대인 값이기 때문에
    • 굳이 탐색하지 않아도 됨. (1->0, 0->1로만 바뀌기 때문)

4. 전체 코드

#include <iostream>
using namespace std;

bool search(string in, int start, int end)
{
	if (start >= end)
		return true;

	int left = start, right = end;

	while (left < right)
		if (in[left++] == in[right--])
			return false;

	return search(in, start, right - 1);
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int tc; cin >> tc;
	while (tc--) {
		string in;
		cin >> in;

		bool ans = search(in, 0, in.size() - 1);
		cout << ((ans) ? "YES\n" : "NO\n");
	}

	return 0;
}

5. 소감

• 중심값을 기준으로 값이 반대여야 한다는 점
• 분할정복을 했을 때 중심값을 기준으로
  • 한쪽 방향으로만 분할정복
  • 한쪽 방향만 탐색해도 양쪽을 탐색하는 효과
• 사실 처음에 풀 때는 문자열의 길이가 짝수인지 체크
  • 문제에 반드시 홀수 입력이 들어온다는 걸 간과하였음.