BOJ 1802 - 종이 접기

문제

백준 온라인 저지 - 1802번

풀이 과정

규칙에 따라 종이를 접었다가 폈을 때 목표로 하는 상태가 될 수 있는지 판단하는 문제입니다.

종이 접기에 의해 생기는 꺾임 방향에는 규칙이 존재합니다.
우선 중심을 기준으로 반으로 접기 때문에 중심 위치의 꺾임 위치는 중요하지 않습니다.
다만 접히는 중심을 기준으로 좌, 우가 서로 대칭을 이루어야 합니다.
따라서 분할 정복 을 통해 대칭성을 판단해서 답을 구해주면 됩니다.

코드

import sys


def check(paper, mid):
    for i in range(mid):
        if paper[i] == paper[mid * 2 - i]:
            return False

    return True


def check_opposite(paper):
    if len(paper) == 1:
        return True

    mid = len(paper) // 2
    ret = check(paper, mid) and check_opposite(paper[:mid]) and check_opposite(paper[mid + 1:])

    return ret


def solution(paper):
    is_opposite = check_opposite(paper)
    return 'YES' if is_opposite else 'NO'


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        paper = sys.stdin.readline().strip()
        answer = solution(paper)
        print(answer)