동호는 종이를 접는데 옆에서 보고 접으려고 한다. 옆에서 본다는 말은 아래 그림과 같이 본다는 뜻이다. 동호는 종이를 반으로 접을 때, 아래와 같이 두가지중 하나로만 접을 수 있다.
오른쪽 반을 반시계 방향으로 접어서 왼쪽 반의 위로 접는다. 오른쪽 반을 시계 방향으로 접어서 왼쪽 반의 아래로 접는다. 아래의 그림은 위의 설명을 그림으로 옮긴 것이다.
한 번의 종이 접기가 끝났을 때, 동호는 종이 접기를 원하는 만큼 더 할 수 있다. 종이 접기를 한번 접을 때 마다 두께는 2배가 되고 길이는 절반이 될 것이다.
종이 접기를 여러 번 했을 때 (안접을 수도 있다), 동호는 종이를 다시 피기로 했다. 그러고 나서 다시 접고 이렇게 놀고 있었다. 옆에서 보고 있던 원룡이는 동호를 위해 종이를 접어서 주기로 했다.(원룡이는 동호의 규칙대로 접지 않는다.) 동호는 그리고 나서 원룡이가 접었다 핀 종이를 다시 동호의 규칙대로 접을 수 있는지 궁금해졌다.
위의 저 종이를 접었다 피면 다음과 같은 그림처럼 펴진다.
종이가 시계방향으로 꺽여있으면 OUT이고, 반시계방향으로 꺾여있으면 IN이다.
종이가 접혀있는 정보가 왼쪽부터 오른쪽까지 차례대로 주어졌을 때, 이 종이를 동호의 규칙대로 접을 수 있는지 없는지를 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1은 위의 그림에서 OUT을 의미하고 0은 위의 그림에서 IN을 의미한다. 예를 들어, 위의 그림과 같은 모양은 100으로 나타낼 수 있다. 문자열의 길이는 3000보다 작으며, 항상 2^N-1꼴이다. (N ≥ 1)
출력
T개의 줄에 차례대로 각각의 종이를 동호의 방법대로 다시 접을 수 있으면 YES를, 접을 수 없으면 NO를 출력한다.
입력 예시
3
0
000
1000110
출력 예시
YES
NO
YES
풀이
어렵게 설명했지만 사실은 쉬운 문제. 문제풀이에 겁먹지 말고 나아가는 자세를 배울 수 있었다. 패턴을 파악하는 게 중요하다.
IN으로 접든, OUT으로 접든 그 결과는 동일하다. 2^N -1개의 길이를 가진 문자열에서, 가운데에 접히는 부분을 기준으로 왼쪽과 오른쪽을 나누면 둘 다 2^(N-1) -1이 된다. 왼쪽을 고정하고 오른쪽을 접는다면...
오른쪽의 접히는 부분은 모두 반대가 되며( 1 -> 0, 0 -> 1 )
접히는 부분의 순서는 역순이 된다.
즉 이렇게 접었을 때 왼쪽과 오른쪽이 포개진다면(즉 왼쪽과 위 규칙을 적용한 오른쪽의 문자열이 같다면) 이 한 번의 접음에서 동호의 규칙을 만족한다. 즉 최소 단위까지 계속해서 위 규칙이 적용되는지 확인해본다면 규칙을 따르는지의 여부를 알 수 있다는 말과 동일하다!
풀이 코드
import sys
input = sys.stdin.readline
T = int(input())
def rev(s) :
result = ''
for _s in s[::-1] :
result += str(1 - int(_s))
return result
def origami(s) :
if len(s) == 1 :
return 1
l = len(s) // 2
left, right = s[:l], rev(s[l+1:])
if left != right :
return 0
return origami(left)
for _ in range(T) :
s = input().strip()
result = origami(s)
print('YES' if result else 'NO')
