물탱크 > 문제은행



문제은행

3231 : 물탱크

제한시간: 3Sec    메모리제한: 256mb
해결횟수: 17회    시도횟수: 65회   



세로 길이가 N, 가로 길이가 M, 높이가 H인 물탱크가 있다. N, M, H는 모두 양의 정수이다. 

<그림 1>은 세로 길이가 2, 가로 길이가 3, 높이가 5인 물탱크 모양을 보여준다. 

<그림 1>에서 보듯이 물탱크 내부는 가로와 세로로 벽이 설치되어 있는데, 

내부 각 칸(즉 사각기둥 모양)의 세로와 가로 길이는 1이고 높이는 H가 되도록 벽이 설치되어 있다. 

이 물탱크를 위에서 내려다보면 <그림 2>와 같이 각 칸이 정사각형인 격자 모양이 된다. 

물탱크 각 칸의 벽에는 물 높이 조정을 위해 구멍이 뚫려 있을 수 있다. 

각 칸에는 네 개의 벽이 있는데, 각 벽 내부에는 최대 한 개의 구멍이 뚫려 있을 수 있다. 

단, 모서리엔 구멍이 없다.

 

5321aa34e52c55673fbbb84628c752ab_1532744
<그림 1>에서 구멍이 있는 높이는 바닥을 기준으로 표시되어 있다. 
구멍의 위치를 위에서 보면 <그림 2>처럼 보이는데 이는 물탱크를 위에서 보았을때 어느 벽, 
어떤 높이에 구멍이 뚫려 있는지를 알려주며, <그림 1>에선 표시하기 어려운 물탱크의 구멍 위치도 표시한다. 
<그림 2>에서 보듯이 물탱크 내부 벽에도 구멍이 있을 수 있다.

5321aa34e52c55673fbbb84628c752ab_1532744
물탱크에 물을 채울 땐, 모든 구멍을 마개로 막아 물이 새지 못하도록 한 후,

격자의 각 칸 위에 설치된 급수 장치를 통해 물탱크 전체를 물로 채운다.

물이 꽉 찬 후에 구멍을 막고 있는 모든 마개를 제거하면 물이 구멍을 통해 인접한 방이나 외부로 흘러나가게 된다. 

어느 정도 시간이 지나면 물이 더 이상 흘러 나가지 않게 되고, 그 때 물탱크 격자의 각 칸에 남아 있는 물의 높이는 서로 다를 수 있다.
참고로, <그림 2>에서 보인 물탱크의 각 칸에 남아 있는 물의 높이를 나타내면 <그림 3>의 괄호 속의 수치와 같다.


5321aa34e52c55673fbbb84628c752ab_1532744
벽의 두께를 무시할 때, 물탱크에 남아있는 물의 총량(부피)을 계산하는 프로그램을 작성하시오.

소스파일의 이름은 watertank.c 또는 watertank.cpp를 권장하지만, 서버에 제출하는 데는 다른 이름도 상관없다.

 



표준 입력으로 다음 정보가 주어진다. 
첫 번째줄에는 물탱크의 세로 길이, 가로 길이, 높이를 나타내는 
세 양의 정수 N, M, H가 차례로 주어진다.

다음 줄에는 첫 번째 가로 벽에 설치된 구멍 정보를 나타내는 M개의 정수가 주어진다.
각 정수는 왼쪽부터 시작하여 순서대로 각 칸의 구멍 높이를 의미한다. 
구멍의 높이는 0 이상 H미만의 정수이다. 
해당 벽에 구멍이 없는 경우는 –1로 표시한다. 
이어지는 줄엔 두 번째 가로 벽에 설치된 구멍 정보가 주어지고, 
이런 식으로 N+1줄에 걸쳐 가로 벽에 설치된 모든 구멍에 대한 정보가 주어진다.

이어지는 줄에는 첫 번째 가로 벽을 공유하는 칸들(<그림 2>에서 맨 윗줄의 칸들)의 세로 벽에
설치된 구멍 정보를 나타내는 M + 1개의 정수가 주어진다. 
각 정수는 첫 번째 세로 벽부터 시작하여 차례로 각 세로 벽의 구멍 높이를 나타낸다. 
그 다음 줄에는 그 다음에 있는 칸들의 세로벽에 설치된 구멍 정보가 주어진다. 
이런 식으로 N 줄에 걸쳐 세로 벽에 설치된 모든 구멍 정보가 주어진다.

참고로, 입출력 예에서 보인 첫 번째 예제는 <그림 2>에서 보인 경우에 대응된다.


물이 더 이상 흘러 나가지 않는 시점에 물탱크에 남아 있는 물의 총량(부피)을 표준 출력으로 출력한다.

[부분문제의 제약 조건]
* 부분문제 1: 전체 점수 100점 중 6점에 해당하며 N = 1, 1 ≤ M, H ≤ 1,000 이고, 세로 벽에는 구멍이 없다.
              즉, 물탱크 세로 벽에 대응하는 구멍의 입력은 모두 –1 이다.
* 부분문제 2: 전체 점수 100점 중 18점에 해당하며 N = 1 , 1 ≤ M, H ≤ 1,000 ​ 이다.
* 부분문제 3: 전체 점수 100점 중 15점에 해당하며 H = 1, 1 ≤ N, M ≤ 1,000​ ​ 이다.
* 부분문제 4: 전체 점수 100점 중 21점에 해당하며 1 ≤ H ≤ 1,000​, 1 ≤ N, M ≤  50  ​이다.
* 부분문제 5: 전체 점수 100점 중 40점에 해당하며 1 ≤ N, M, H ≤ 1,000 ​ 이다.

[Copy]
2 3 5
1 -1 -1
3 2 -1
4 -1 2
-1 -1 4 3
-1 -1 -1 -1
[Copy]
17


[Copy]
1 5 10
5 -1 -1 -1 6
-1 7 -1 6 -1
-1 2 8 4 2 3
[Copy]
20






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.