이동식 저장소

14719. 빗물 본문

Problem Solving/BOJ

14719. 빗물

해스끼 2023. 3. 25. 16:04
 

14719번: 빗물

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치

www.acmicpc.net

블록 사이에 빗물이 얼마나 고이는지 구하는 문제이다. 2차원 공간의 바닥은 막혀 있다고 가정한다.

 

바닥이 막혀 있으므로 물이 빠져나갈 수 있는 방향은 왼쪽 또는 오른쪽이다. 설마 물이 위로 증발하지는 않을 것이고.. 그렇다면 블럭을 제외한 모든 빈 공간을 물로 채운 후, 왼쪽 또는 오른쪽으로 빠져나가는 물을 제외하면 된다.

 

2차원 공간에 다음과 같이 물을 채운다. 검은색은 블록이다.

왼쪽과 오른쪽으로 물이 얼마나 빠져나갈 수 있는지 시뮬레이션해 보자. 방법은 간단하다. 양 끝에서 출발하여 블록을 만날 때까지 물을 지우면 된다.

이제 2차원 공간에 남은 물의 양을 세면 된다.

저작자표시 비영리 변경금지

'Problem Solving > BOJ' 카테고리의 다른 글

1572. 중앙값  (0) 2023.04.10
1615. 교차개수세기  (0) 2023.03.30
20925. 메이플스토리  (0) 2023.03.25
13418. 학교 탐방하기  (0) 2022.12.01
1445. 일요일 아침의 데이트  (0) 2022.11.29
'Problem Solving/BOJ' Related Articles more
Comments