[백준 / BOJ] 8982 수족관 1

문제

출처 : www.acmicpc.net/problem/8982

8982번: 수족관 1

물이 들어있는 수족관이있다.

수족관의 바닥에 구멍이 뚫려있을때, 각 구멍을통해 빠져나간후 남은 물의 양을 구하는 문제다.

 

풀이

범위가 크지않아 완전탐색으로도 풀리는 문제다.

 

각 구멍의 좌표를 기준으로 왼쪽, 오른쪽으로 탐색하며 현재의 높이보다 수족관의 바닥의 높이가 높을경우, 높이를 올려주며 남아있는 물의 양을 구해주면된다.

 

1. 구멍이 있는 바닥의 x1(시작 x 좌표) 부터 시작해서, x2(끝 x 좌표)미만 까지 모든 물을 빼준다. (구멍이있는 타일은 물이 남아있을수없음)

 

2. 높이를 구멍이 있는바닥의 높이로 초기화하고, x1-1부터 0 까지 , x2부터 끝까지 탐색을 해준다.

 

3. 이때, 현재 높이가 현재 보고있는 바닥의 높이보다 낮을경우, 현재 높이를 바닥의 높이로 초기화 하고 물의 높이를 바꾼다.

 

4. 반대로 현재높이보다 바닥의 높이가 낮다면, 초기화 하지않고, 물의 높이를 바꾼다.

 

(3,4번 과정에서 이미 다른구멍에 의해서 물이 더 많이빠져있을 경우가있다. 따라서, 현재 물의 높이보다 남아있는 물의 높이가 많을경우에만 물의 높이를 갱신해줘야한다.)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/8982%20%EC%88%98%EC%A1%B1%EA%B4%80%201/main.cpp

devxb/JJUNalgo