BOJ 1802 - 종이 접기

문제 링크

주어진 In,Out을 따라 그림을 그려보면 쉽게 규칙을 찾을 수 있다.

해당 종이를 반으로 접기 위해서는 가운데를 기준으로 접었을때 만나는 것들끼리 비교해야 한다.
길이가 n이고, 가운데 인덱스가 mid일때
paper[0]과 paper[n-1], paper[1]과 paper[n-2], ... paper[mid-1]과 paper[mid+1]
끼리 비교해야 하는데 두 값이 달라야만 접을 수 있다.

길이가 1이 될때까지 접히면 YES, 못접으면 NO 를 출력한다.

def fold(s):
    li = list(map(int, list(s)))
    reversed = list(map(lambda x: str((x+1) % 2), li))
    reversed.reverse()
    return ''.join(reversed)


def can_fold(paper):
    if len(paper) == 1:
        return True
    mid = len(paper)//2
    x = paper[:mid]
    y = fold(paper[mid+1:])
    if x == y:
        return can_fold(x)
    return False


T = int(input())

for _ in range(T):
    paper = input()
    if can_fold(paper):
        print("YES")
    else:
        print("NO")