3월의 퍼즐에 참여해주신 모든 분들께 감사드리며, 
참여해주신 분들 중 정답과 함께 좋은 풀이를 보내주신  
조힘찬빛 님에게 문화상품권을 전달하겠습니다.

3월의 퍼즐 문제

 

시작하기에 앞서, 문제를 풀기에 유용한 사실 하나를 소개한다.


위와 같이 \(3 \times 4 \) 사각형이나 \(4 \times 3 \) 사각형을 어느 곳에서 따오든 간에 하늘색 두 부분에 있는 건물 수가 서로 같고 또 초록색 두 부분에 있는 건물 수가 서로 같다. 이는 아주 쉽게 보일 수 있다.

건물이 들어설 평야를 적갈색으로, 건물이 들어서지 않는 평야를 회색으로 칠하도록 하자. 먼저 다음과 같은 세 구역을 칠해야 하는 것은 당연하다.


그러고 나면 노란색으로 칠한 두 구역 중 하나만을 칠해야 한다. 둘 중 어디를 칠해야 할까? 일단 아래쪽의 것을 택하고 계속 진행해 보자.


맨 처음 언급한 사실을 활용하여 진행하면 일단 위의 그림처럼 총 네 개의 행이 확정이 된다.

그 바로 위의 행을 보자. 건물을 아무 데나 하나 지으면(안 지을 순 없다), 그 양옆 2칸씩 총 4칸은 회색이 된다. 또 맨 처음 언급한 사실을 이용하면 건물을 지은 곳 왼쪽 3칸째와 오른쪽 3칸째는 건물을 지을 수밖에 없다. 이것이 행을 다 채울 때까지 반복이 되어 결국에는 건물을 지은 자리로부터 가로로 3의 배수만큼 떨어진 자리에 건물이 들어서고 나머지는 비게 된다.

이런 식으로 행을 하나하나 확장할 때마다 똑같은 일이 벌어진다. 3칸마다 한 번씩 총 5채의 건물을 짓고 나머지는 비워 둬야 한다. 그런데 이런 확장이 (노란색으로 표시한) 위에서 4번째 행에서는 불가능하다. 3으로 나눈 나머지가 0인 곳, 1인 곳, 2인 곳에 모두 산지가 있기 때문이다. 따라서 이렇게는 조건에 맞게 건물들을 지을 수 없고, 이는 두 구역 중 아래쪽의 것을 선택하면 안 된다는 것을 의미한다.

다시 돌아가 둘 중에 오른쪽을 택하고 진행해 보면, 건물이 들어설지 들어서지 않을지 여부가 모든 칸에 대해 차근차근 논리적으로 결정이 된다. 진행하는 데 아까 언급한 사실이 계속 도움이 된다. 그 결과 정답은 다음과 같다.



다음은 3월의 정답자로 선정된 조힘찬빛님의 풀이입니다.

조정휘
KAIST 수리과학과 석박사통합과정 KPP(Korean Puzzle Party)