창고 털기 timer 1s memory 256MB

때는 서기 1570년, 선조 4년.

의적 반디는 탐관오리들이 못된 방법으로 빼앗은 백성들의 재물을 훔쳐 다시 백성들에게 나누어주고 있었다. 동에 번쩍 서에 번쩍 반디가 출몰하자, 가장 악랄하다고 알려진 사또 중 하나인 정현은 창고 보안을 강화하기로 했다.

그 시절에는 감시 카메라가 없었으므로, 다음과 같은 방법을 사용했다. 창고의 정면도, (왼쪽)측면도, 평면도를 그려놓고, 매 시간 확인했을 때 그 중 하나라도 변하면 고을에 비상계엄을 선포하여 도둑을 잡는 것이다.

쌀 한가마는 편의상 1x1x1모양의 큐브라고 생각하자.(? 그냥 그렇다면 그런거다.) 따라서 쌀가마가 쌓여진 창고는 2차원 공간에 각 격자에 쌀가마가 쌓여진 높이로 형상화 할 수 있다. 이 때 삼면도를 그리는 것은 간단하다.

예를 들어 다음과 같다.

이렇게 삼면도를 그려놓고, 그것의 변화를 감지하면, 굳이 24시간 경계를 서지 않고도 사또 정현은 창고를 지킬 수 있게 된다는 것이다. 사또 정현의 관료들은 백성들의 재물 강탈에 힘 써야하기 때문에, 24시간 창고 경계를 할 시간이 없다.

그러나 의적 반디가 누구인가. 그는 홍길동전의 모티브가 된 사나이일지도 모르는, 그 시절 조선 제일의 의적 아닌가. 반디는 삼면도가 변하지 않는 선에서 최대한으로 쌀가마니를 털어가려고 한다.

예를 들어 위 그림과 같이 털어간다면, 삼면도는 변하지 않는다. 어떤 칸은, 삼면도를 유지시키기 위해 의도적으로 쌀가마니를 더 쌓을 수도 있음을 유의한다.

시대는 변하고, 탐관오리라는 존재는 없어졌지만, 우리는 그 시절 의적 반디를 기약하며 프로그래밍하기로 하자. 창고의 상태가 주어졌을 때, 앞에서 본 정면도, 왼쪽에서 본 측면도, 위에서 본 평면도를 건드리지 않고 털어갈 수 있는 가장 많은 쌀가마의 수를 출력하는 프로그램을 작성하라.​