[Python] 백준 1802번: 종이 접기(시간 복잡도 1등)

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

1802번: 종이 접기

import sys
input = sys.stdin.readline


def isAvailableStr(str):
    todo = list(str)

    while len(todo) >= 3:
        for i in range(2, len(todo), 2):
            if todo[i-2] == todo[i]:
                return False

        nextTodo = []
        for i in range(1, len(todo), 2):
            nextTodo.append(todo[i])

        todo = nextTodo

    return True


T = int(input())
for _ in range(T):
    curInput = str(input().rstrip())

    if isAvailableStr(curInput):
        print("YES")
    else:
        print("NO")

문제 이해에 많은 시간을 쏟은 문제였다. 다음 그림을 보자.

앞으로의 설명을 도와줄 'V 표시'에 대한 설명이다. V가 있으면 위 사진과 같이 접겠다는 의미이다. 이것을 바탕으로 설명하겠다.

위 사진에서 0과 1은 각각 문제에서 주어진 바와 같이, 각각 in과 out을 의미한다. 위의 사진에서 얻을 수 있는 단서는 다음과 같은 것들이 있다.

1. 1번 접혀서 만들어진 2개의 선분은, 종이를 접을 때 서로 영향을 미친다.

2. 2개의 선분을 접음으로써 생겨나는 0, 1은, 서로 같지 않다.

 

그럼 문제를 어떻게 풀어나가야 할까?

다음은 0부터 시작해서 계속해서 종이를 접을 때의 상태를 나타낸다.

패턴이 보이기 시작한다. 그렇다면, 100111001000110이 input으로 들어온다면, 처음에는 100111001000110에 대해서, 다음에는 0110001, 100 순서로 위에서 확인한 조건을 체크해주면 된다. 이것을 일반화 하면, 특정 문자열에 대해, 인덱스를 1부터 시작해서 2씩 증가시켜주면서 각 원소를 담은 문자열이 그 다음 문자열이 되겠다.