백준 8982. 수족관 1

https://www.acmicpc.net/problem/8982

8982번: 수족관 1

 

문제 해결 방법을 떠올리기 까지 좀 걸린 문제였다. 

처음에는 주어지는 꼭짓점들로 어떻게 배열을 구성할지 고민했다.

하지만 이 문제는 그렇게 하지 않고, 주어지는 꼭지점들로 각 열들의 깊이만 구성하면 된다.

 

예를들어 주어지는 input이 다음과 같다면 

14
0 0  
0 5
1 5
1 3
2 3
2 4
3 4
3 2
5 2
5 4
6 4
6 3
8 3
8 0
2
1 3 2 3
3 2 5 2

첫째 줄에 꼭지점의 수 14가 주어진다.

그리고 두번째 줄은 (0,0)이고 세번째 줄부터 보면 되는데,

세번째 줄 부터는 두 줄 씩 짝지어 보면 된다.

 

예를들어 3번 줄은 (0,5)고 4번 줄은 (1,5)인데 이는 첫 번째 열의 깊이가 5라는 의미다.

또 다른 예로는 9번째줄은 (3,2)고, 10번째 줄은 (5,2)인데 이는 4,5번 열의 깊이가 2라는 의미다.

 

이렇게 열 별로 깊이를 depth[]에 저장하면, 각 열의 깊이를 뜻하는 depth[]는 다음과 같아진다.

5 3 4 2 2 4 3 3

 

그리고 구멍에 관한 정보는 다음과 같이 주어지는데 

2
1 3 2 3
3 2 5 2

첫 번째 구멍은 (행,열)로 따지면 (3,1)과 (3,2) 수평선분의 가운데에 있다는 의미인데, 어처피 수평끼리는 깊이가 같기 때문에 다 필요 없고 첫 번째로 주어지는 값 1 만이 중요하다. 

1은 곧 우리가 구한 depth[]의 depth[1] 위치에 구멍이 존재한다는 의미다.

 

 

이제 구멍을 하나씩 열면서 물을 빼보면 된다.

depth[]에서 구멍의 위치 기준 왼쪽, 오른쪽으로 이동하면서 구멍의 깊이 보다 현재 깊이가 깊으면 (현재 구멍의 깊이 - 구멍의 깊이)가 남은 물의 높이가 된다.  이때 여러 구멍들을 탐색할것이기 때문에 해당 열의 물의 높이와, 새로 구한 물의 높이 중 작은 값을 택해야 한다. 

 

현재 깊이가 구멍의 깊이 보다 같거나 작다면, 해당 위치 이후로는 물이 빠지지 않는 것을 의미한다. 

따라서 해당 열의 물의 높이는 0이 되고, 그 이후로는 구멍의 깊이가 아닌 현재 위치의 깊이와 비교해야 한다.