백준 - 빗물 (JAVA)

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

14719번: 빗물

 

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

2차원 배열의 가로, 세로 크기와 각 배열의 블록 개수 (그림 기준 까만색 칸의 개수)가 차례로 주어진다면 빗물이 최대한 얼마나 고일 수 있는지 구하는 문제이다.

 

---

#1 첫번째 시도

 

for문을 최소한으로 돌기 위해 입력 받는 반복문에서 바로 빗물이 고일 수 있는 칸을 더하려고 했다.

하지만 현재 인덱스 기준으로 오른쪽에 벽이 있는지 없는지 알 수가 없어서... (입력 받기 전이니까)

해당 시도는 실패로 돌아갔다.

 

 

#2 두번째 시도

 

for문을 돌리면서 빗물이 고일 수 있는 left index와 right index를 구해서 그 사이의 빗물을 구하려고 했다.

그런데 빗물이 고일 수 있는 기준이 모호했다.

아예 빗물이 고이지 않는 예시가 나올수도 있고, left index와 right index를 구한다해도 그 사이에 고일 수 있는 빗물을 계산하기 위해 또 반복해야 했다. 

 

#3 세번째 시도

class Main {
    public static void main(String[] args) {
        // h, w, arr 입력 받기

        // 로직
        for(int i=1;i<w-1;i++) {
            int rIndex = w-1;
            int lIndex = 0;
			
            // left biggest
            for(int j=0;j<i;j++) {
                lIndex = arr[lIndex] > arr[j] ? lIndex : j;
            }
			
            // right biggest
            for(int j = w-1;j>i;j--) {
                rIndex = arr[rIndex] > arr[j] ? rIndex : j;
            }
			
            int index = arr[lIndex] < arr[rIndex] ? lIndex : rIndex;
            if(arr[index] > arr[i])
                answer += (arr[index] - arr[i]);
        }
		
        System.out.println(answer);
    }
    
}

 

입력 값 받는 부분은 생략했다.

for문을 i = 1... w-2까지 돌면서 현재 인덱스 기준 왼쪽의 가장 큰 벽, 오른쪽의 가장 큰 벽을 구했다.

왼쪽 오른쪽 벽 중에서 더 작은 값을 구하고 고일 수 있는 빗물을 구해 answer에 더했다.