[BAEKJOON][Python] 1802 - 종이 접기

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

---

✏️ 풀이 과정

📝 접근

• 주어진 규칙에 만족하기 위해서는 대칭이 되는 부분이 서로 반대 방향으로 접혀있어야 한다.

• 접힌 부분을 절반으로 분할하여 더이상 분할할 수 없을 때까지 항상 위의 규칙을 만족해야 한다. 따라서 이 문제는 분할 정복을 활용하여 해결할 수 있다.

• 왼쪽 부분 문제가 규칙을 만족할 경우 오른쪽 부분 문제 역시 규칙을 만족할 것이다. 왼쪽 부분 문제와 오른쪽 부분 문제가 서로 대칭인 경우에만 재귀 함수가 호출되기 때문이다.

✨ 소스 코드

import sys
input = sys.stdin.readline

def solve(left, right):
	# 기저 사례: 접힌 부분이 없을 때
    if left == right: return True

    i, j = left, right
    while i < j:
        if folded_paper[i] == folded_paper[j]: return False
        i, j = i + 1, j - 1

	# 왼쪽 부분 문제와 오른쪽 부분 문제는 서로 대칭이므로, 오른쪽 부분 문제에 대해서는 고려하지 않아도 된다.
    return solve(left, (left + right) // 2 - 1)

for _ in range(int(input())):
    folded_paper = str(input()).rstrip()
    print('YES') if solve(0, len(folded_paper) - 1) else print('NO')