📚 1802 - 종이 접기

종이 접기

이해

이분 탐색 문제이다.

항상 종이를 절반씩 접는다고 할 때, 제시된 문자열로 종이를 접을 수 있는지 확인하는 문제이다.
종이를 절반씩 접게 되면, 항상 접은 부분을 중심으로 양쪽에는 반대로 접힌 흔적이 남게 된다.

• 종이의 길이가 홀수이다.
• 1 : OUT, 종이가 시계 방향
• 0 : IN, 종이가 반시계 방향

ex) 1000110 인 경우
011
100

→ 1 0

이와 같이 종이를 절반씩 접어가면서, 좌우 값이 같지 않은지 확인하다.

• 같으면 방향이 겹치므로 접을 수 없다.
• 다르면 방향이 겹치지 않아 계속 진행한다.

소스

import sys  
  
read = sys.stdin.readline  
  
t = int(read())  
  
  
def verify(start, end):  
    if start >= end:  
        return True  
  
    left = start  
    right = end  
  
    # 이분 탐색  
    while left < right:  
  
        if paper[left] == paper[right]:  
            return False  
  
        left += 1  
        right -= 1  
  
    return verify(start, right - 1)  
  
  
for _ in range(t):  
    paper = list(map(int, read().rstrip()))  
  
    if verify(0, len(paper) - 1):  
        print("YES")  
    else:  
        print("NO")