[8월의 퍼즐] 괄호를 닫아라!

수학에서는 연산의 순서를 표기하기 위해 괄호를 사용한다. 한때 소셜 미디어를 뜨겁게 달군 식 6÷2(1+2)는, 답이 1인지 9인지에 대한 사람들의 의견이 분분해 논란이 되었다. 2(1+2)를 먼저 계산하면 1이 되지만, 6÷2를 먼저 계산하면 9가 되기 때문이다. 물론 논란이 발생한 이유는 2와 (1+2) 사이에 생략한 곱셈 기호를 나눗셈보다 먼저 계산하는지 아닌지가 모호하기 때문이지만, 만약 괄호를 써서 확실하게 6÷(2(1+2))나 (6÷2)(1+2)와 같이 표현했더라면 아무런 논란거리가 되지 않았을 것이다.

이번 퍼즐의 주인공은 사칙연산 순서는 아니고, 바로 괄호다. 6÷(2(1+2))와 (6÷2)(1+2)에서 숫자와 연산 기호를 제거하고 괄호만 남겨 보면 각각 (()), ()() 가 된다. 이와 같이 괄호만으로 구성된 문자열(문자들의 배열)을 괄호 문자열이라고 한다. 물론 아무렇게나 괄호들을 배열한다고 해서 올바른 괄호 문자열이 되는 것은 아니다. 예를 들어, 위에서 언급한 (()) 와 ()() 는 올바른 괄호 문자열이지만, (() 는 바깥쪽 괄호를 마저 닫아주지 않아서 잘못된 괄호 문자열이고, )() 는 괄호를 열기 전에 닫아버렸기 때문에 잘못된 괄호 문자열이다.

또, 이번 퍼즐에서는 (), {}, [], ⟨⟩ 이렇게 총 네 가지 종류의 괄호를 사용할 것이다. 초등학생 때는 대괄호 안에 중괄호, 중괄호 안에 소괄호를 써야 한다고 배우지만, 이번 퍼즐에서는 괄호를 사용하는 순서는 무시하도록 하자. 올바른 괄호 문자열을 만들기 위해서는 그저 같은 종류의 괄호끼리 쌍을 지어 열고 닫기만 하면 된다. 예를 들어, ([]) 나 {}⟨⟩ 는 같은 종류의 괄호끼리 쌍을 지었기 때문에 올바른 괄호 문자열이지만, ([)] 는 잘못된 괄호 문자열이다. 올바른 괄호 문자열의 엄밀한 정의가 필요한 독자들을 위해 글 마지막에 더 자세한 설명을 적어 놓았다.

이제 본격적으로 퍼즐을 소개한다. 다음 그림과 같이 5×10 직사각형 모눈종이의 한쪽 면에 잘못된 괄호 문자열이 적혀 있다.

이 종이의 격자선을 따라 잘라서 여러 조각으로 만든 뒤, 조각들을 재배열해서 다시 5×10 직사각형으로 만들려고 한다. 각각의 조각은 하나의 연결된 종이여야 하고, 꼭짓점끼리 아슬아슬하게 연결된 것은 하나의 조각으로 치지 않는다. 조각을 회전할 수는 있지만 뒤집을 수는 없다.

완성된 직사각형에는 올바른 괄호 문자열이 적혀 있어야 한다. 완성된 직사각형에서 괄호 문자열은 어디에 위치해도 상관없지만, 반드시 가로로 연속된 8칸을 차지해야 한다. 예를 들어, 아래에서 왼쪽 그림과 같은 모양을 만드는 것은 가능하지만 오른쪽 그림과 같은 모양을 만들면 안 된다.

가장 간단하게 떠오르는 방법은 맨 오른쪽의 열린 괄호 4개를 제자리에서 180° 회전하는 것이다. 아래 그림과 같이 자르면 4개의 정사각형 조각과 구멍 난 5×10 종이, 이렇게 총 5개의 조각이 필요하다.

KPP의 안진후 님은 다음과 같은 참신한 4조각짜리 풀이를 찾아냈다.

하지만 조각의 수를 더 줄이는 것도 가능하다. 가능한 한 적은 개수의 조각으로 잘라 재배열해서, 올바른 괄호 문자열을 만드는 방법을 찾아 보자! 여러 가지 방법이 존재할 수 있으니, 꼭 최소 개수가 아니더라도 다양하고 창의적인 답안의 공유를 환영한다.

기사 앞에서 올바른 괄호 문자열이 무엇인지 설명했지만, 엄밀한 정의를 내리지는 않았다. 혹시 궁금해할 독자들을 위해 엄밀한 정의를 적어 두겠다. 올바른 괄호 문자열은 다음과 같이 재귀적으로 정의된다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. 문자열 S 가 올바른 괄호 문자열일 때, (S), {S}, [S], ⟨S⟩ 는 올바른 괄호 문자열이다.
3. 문자열 S, T 가 올바른 괄호 문자열일 때, ST 는 올바른 괄호 문자열이다.
4. 위 규칙을 통해 만들 수 없는 괄호 문자열은 잘못된 괄호 문자열이다.

예를 들어, 다음과 같이 ([]){} 가 올바른 괄호 문자열임을 보일 수 있다. (빈 문자열) → [] → ([]), (빈 문자열) → {} 와 같이 두 개의 올바른 괄호 문자열을 찾을 수 있으므로, 두 문자열을 합친 ([]){} 는 올바른 괄호 문자열이다. 반면, ([)] 는 위 규칙을 통해 만들 수 없으므로 잘못된 괄호 문자열이다.