[BOJ 14719] 빗물 (G5)

📍 문제 

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

 

📍 문제 풀이

 

빗물이 고이기 위한 조건은 아래와 같다.

• 마지막열은 물이 고일 수가 없다.
• 현재 블록의 높이보다 높은 블럭이 존재해야한다.

현재 블록을 반복문으로 위치를 변경하며 왼쪽 오른쪽에서 가장 높은 블록을 구한 다음, 

현재 블록보다 둘 다 높다면 물이 고일 수 있기 때문에

왼쪽, 오른쪽 둘 중에 더 낮은 블록을 기준으로 낮은 블록에서 현재 블록의 높이를 빼주어 고인 물의 양을 구해 더해준다.

 

 

 

📍 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_14719 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int h = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());

		int[] heights = new int[w];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < w; i++) {
			heights[i] = Integer.parseInt(st.nextToken());
		}

		int result = 0;
		for (int i = 1; i < w - 1; i++) {
			int left = 0;
			int right = 0;

			for (int j = 0; j < i; j++) {
				left = Math.max(left, heights[j]);
			}

			for (int j = i + 1; j < w; j++) {
				right = Math.max(right, heights[j]);
			}

			if (heights[i] < left && heights[i] < right) {
				result += Math.min(left, right) - heights[i];
			}
		}
		System.out.println(result);
	}
}