성빈이는 새로 이사를 가면서 자신의 방에 가구를 배치했다. 그러나 성빈이는 아직 침대를 배치하지 않았다. 성빈이는 침대를 어떻게 배치할지 견적을 보고 있다.

성빈이의 방은 가로 M, 세로 N 크기의 격자 모양으로 이루어졌으며 침대는 1 × D 크기이다. 침대는 90도 돌려서 배치할 수 있으며, 30도, 60도 등의 다른 각도로는 돌릴 수 없다. 또, 침대는 정확히 격자에 맞게 배치해야 하고 다른 가구나 벽이 있는 곳에는 침대를 놓을 수 없다. 아래 사진은 성빈이가 방에 침대를 배치할 수 있는 모든 경우를 나타낸다.

성빈이를 도와 방의 정보가 주어지면 침대를 놓는 방법의 수를 구하는 프로그램을 작성하여라.

#3030 upload 373회 done 193회 how_to_reg 170명

침대 timer 1초 memory 128MB

#3030

침대 1초 128MB