백준 1802. 종이 접기

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

1802번: 종이 접기

 

분할정복 문제.

음 .. 풀긴 했는데 뭔가 복잡하게 푼 느낌? 더 간단히 풀수 있는 방법이 있을것 같다.

 

처음에 문제 이해가 좀 복잡하긴 한데 결국 이 문제는 종이의 접히는 부분이 주어 졌을때, 그 종이의 가운데를 계속 접히는 방향으로 접었을때 끝까지 접을수 있는지 없는지 판단하는 것이다.

다음과 같이 주어진다면

 

1000110

가운데가 0 이기 때문에 오른쪽 부분이 반시계 방향으로 이동해 다음과 같게 된다

 

100

100

이렇게 되는 이유는 (1000110)의 오른쪽 부분 (110)이 왼쪽 부분 (100)의 위로 오고, 이때 반시계 방향으로 돌기 때문에 옆에서 봤을때 접힌 부분이 반대로 되기 때문에 오른쪽 부분 (110) -> 반시계 방향으로 돌면서 (011) -> 옆에서 봤을때 접힌 부분이 반대로 되어서 (100)이 된다.

 

이렇게 새로운 종이들이 생기게 되고, 가운데 부분이 모두 같은 경우에만 또다시 접을수 있다.

만약 접다가 가운데 부분이 서로 다른 경우가 있다면 더이상 접을수 없게된다.