[Java] 백준 14719번: 빗물

[문제 바로 가기] - 빗물

💡 접근 방식

창고 다각형 문제와 비슷한 문제로 창고 다각형 풀이에서 창고의 골격(?)을 빼주면 된다.

가장 큰 기둥을 기준으로 왼쪽과 오른쪽의 (빗물이 찰 넓이 + 골격 넓이)를 구해준다. 그리고 가장 큰 기둥의 높이를 더하고 골격의 넓이를 빼주면 끝!

풀이

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

/**
 * 백준 14719번 빗물
 * - 2304번 창고 다각형과 비슷한 문제로 창고 다각형에서 골격을 빼주면 된다
 */

public class Main {
	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());
		
		List<Integer> list = new ArrayList<>();
		st = new StringTokenizer(br.readLine());
		
		int max = -1;
		int maxIndex = -1;
		int sum = 0;
		
		for (int i = 0; i < W; i++) {
			int height = Integer.parseInt(st.nextToken());
			list.add(height);
			
			sum += height;
			
			if (max < height) {
				max = height;
				maxIndex = i;
			}
		}
		
		int skeleton = 0;
		
		for (int i = 0; i < maxIndex; i++) {
			for (int j = i + 1; j <= maxIndex; j++) {
				if (list.get(i) <= list.get(j)) {
					skeleton += (j - i) * list.get(i);
					i = j;
				}
			}
		}
		
		for (int i = W - 1; i > maxIndex; i--) {
			for (int j = i - 1; j >= maxIndex; j--) {
				if (list.get(i) <= list.get(j)) {
					skeleton += (i - j) * list.get(i);
					i = j;
				}
			}
		}
		
		if (skeleton == 0) System.out.println(0);
		else System.out.println(skeleton + max - sum);
	}
}