취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1802번 문제인 종이 접기이다.
문제는 아래 링크를 확인하자.

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

동호의 규칙대로 종이를 접는다는 것은 매 상태의 종이를 양 끝이 맞닿게끔 접는 것을 의미한다. 이 때 접히는 가운데가 어느 쪽으로 접혀있는지와는 무관하게, 접었을 때 만나게 되는 쌍의 위치들의 접힌 방향이 서로 반대여야 함을 확인하자. 이는 반이 접혀 포개져있는 종이를 회전시켜 지금의 모양으로 만들었다고 생각하면 그 접힌 방향이 반대방향으로 보이게 되는 것을 관찰하는 것으로 알 수 있다.

만약 모든 쌍들이 정확히 반대를 이루지 못한다면 동호의 규칙대로 종이를 접는 것은 불가능하다고 판단하자. 그렇지 않은 경우 그 반으로 접힌 종이에 대해 종이 접기가 끝난 상황이 아니라면 이 종이를 다시 동호의 규칙대로 접을 수 있는지를 판단하자. 만약 종이 접기가 끝난 상황이라면 동호의 규칙대로 종이를 접는 것은 가능하다고 판단하자.

글쓴이는 위의 과정을 함수를 작성해 재귀적으로 구현하였다.

아래는 제출한 소스코드이다.

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

int T;
string s;

bool func(int L, int R) {
	if (L == R) return 1;
	int mid = (L + R) / 2;
	for (int i = mid - 1, j = mid + 1; i >= L; i--, j++) {
		if (s[i] == s[j]) return 0;
	}
	return func(L, mid - 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) {
		cin >> s;
		if (func(0, s.length() - 1)) cout << "YES\n";
		else cout << "NO\n";
	}
}