홍수 피해 조사 timer 1s memory - MB

홍수 피해를 예방하기 위해 여러 가지를 연구하는 지헌이는 블록들을 가지고 시뮬레이션을 하고 있다. 시뮬레이션에 사용되는 지형 모형은 어떤 지역의 고도 정보를 담고 있다. 경사까지 고려하면 너무 복잡하므로 지형 모형은 N×M 크기의 직사각형 격자판에 블록들을 세로로 쌓은 것으로 고려한다.

모든 지형 모형들은 아래의 그림과 같이 N×M 크기의 직사각형 격자에 블록의 높이를 써넣음으로 나타낼 수 있다. 각 칸은 가로와 세로의 길이가 모두 1인 정사각형이므로, 각 칸이 차지하는 면적 또한 1이 된다.

여러 가지 지형 모형들을 가지고 모의실험을 하던 지헌이는 실수로 이모형을 수조에 떨어뜨렸다. 지형 모형에 사용되는 블록들은 밀도가 크기 때문에 수조의 바닥으로 가라앉는다. 이 모형들을 수조 위로 들어 올리자, 물이 다시 수조로 떨어졌으나 지형의 고도 때문에 고도가 낮은 곳에는 물이 고여 있게 되었다. (참고 : 수조는 충분히 깊다)

이 현상에 재미를 느낀 지헌이는 자기가 가지고 있던 지형 모형들이 수조 속에 들어갔다 나오면, 고여 있게되는 물의 부피를 계산하려 한다. (단, 수조에서 꺼낼 때는 똑바로 세워서 그대로 꺼내기 때문에 비스듬하게 흘러내리는 물은 없다고 가정하자.) 임의의 칸에 고여 있는 물의 부피는, 그 칸에 고여 있는 물의 높이로 계산할 수 있다. (각 칸의 밑넓이는1이므로)

예를 들어, 위에 제시된 지형 모형을 수조 속에 넣었다 꺼내면 물은 위의 그림과 같이 3개의 칸에 고여 있게 된다. 수면의 높이는 3이므로, 총 물의 부피는 2 + 1 + 2 = 5 가 된다. 이제 지헌이가 갖고 있는 지형 모형의 정보가 주어지면, 이모형을 수조 속에 넣었다 꺼냈을 때 고여 있는 총 물의 부피를 계산하는 프로그램을 작성하여야 한다.