Boj 1802) 종이 접기

문제

백준 1802

설명

이 문제는 종이를 반으로 접는다. 이때 종이가 나뉘는 두 부분을 L 파트와 R 파트라고 하자.

이 때 L 파트의 접힌 방향은 접은 방법과 같다. 왜냐하면 종이를 반으로 접을 때 R 파트만 움직이고 L 파트는 그대로 남아있기 때문이다. 이를 이용해 접은 순서를 얻을 수 있다.

그리고 한번 접을 때 마다 R 파트는 뒤집어진다. 그래서 한번 더 접으면 R 파트의 L 파트가 움직이고 R 파트의 R 파트는 그대로 있게 된다. 따라서 R 파트는 계속 접힌 방법의 반대 방향으로 꺾여있게 된다.

이를 재귀적으로 계산하면 풀리는 문제이다.

시간 복잡도

O(\(\mathrm{N}\))

코드

string in;
string order;
bool Do(int l, int r, int th = 0, bool bReverse = false)
{
	if (r < l) return true;

	int m = (l + r) / 2;
	if ((in[m] == order[th]) == bReverse) 
		return false;

	if (!Do(l, m - 1, th+1, false)) return false;
	if (!Do(m + 1, r, th+1, true)) return false;
	return true;
}

int main(void)
{
	int T; cin >> T;
	while (T--)
	{
		cin >> in;
		order = "";
		for (int i = in.size(); i > 0; i >>= 1)
			order.push_back(in[i>>1]);
		cout << (Do(0, in.size()-1) ? "YES" : "NO") << '\n';
	}
}