[JAVA][BOJ][G5] 14719. 빗물

14719번: 빗물

문제

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

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

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

풀이

[java][boj][s2] 2304. 창고 다각형

창고 다각형과 유사한 문제지만 다른 방법으로 풀었다(사실 기억이 안났다) 창고 다각형에서 기둥의 크기만 전부 더해서 빼 주면 되지만 어쩌다 보니 더 간단하게 문제를 풀 수 있었다

풀이를 정리해 보려고 했지만 설명이 복잡해서 코드에 주석을 달아 풀이를 해봤다

코드

package 구현;

import java.io.*;
import java.util.*;

public class g5_14719_빗물 {

	public static void main(String[] args) throws Exception {
		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[] arr = new int[W];
		
		// 가장 높은 기둥
		int max = 0;
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < W; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			max = Math.max(max, arr[i]);
		}
		
		// 현재 기둥의 높이(빗물의 기준이 된다)
		int height = 0;
		// 모인 빗물(웅덩이 한 개)
		int tmp = 0;
		// 모인 빗물들의 합
		int sum = 0;
		
		// 왼쪽부터
		for (int i = 0; i < W; i++) {
			// 현재 기둥의 높이보다 낮은 기둥에서는 빗물이 고인다
			if(height > arr[i]) tmp += height-arr[i];
			// 현재 기둥보다 높거나 같은 높이의 기둥을 만난다면 웅덩이에 고인 빗물의 값을 더해 준다
			// 다음 웅덩이도 구해야 하므로 웅덩이의 값을 0으로 초기화
			// 현재 기둥의 값을 다음 기둥의 값으로 초기화
			else {
				sum += tmp;
				height = arr[i];
				tmp = 0;
			}
		}
		
		height = 0;
		tmp = 0;
		
		// 오른쪽부터
		// 왼쪽부터 구하는 경우, 가장 높은 기둥 중 가장 오른쪽에 있는 기둥 이후로는 빗물의 값이 더해지지 않음
		// 위의 식에서 구하지 못한 빗물의 값(가장 높은 기둥 중 가장 오른쪽에 있는 이후의 빗물의 값)을 오른쪽부터 구함
		for (int i = W-1; i >= 0; i--) {
			if(height > arr[i]) tmp += height-arr[i];
			else {
				sum += tmp;
				height = arr[i];
				tmp = 0;
			}
			
			// 가장 높은 기둥 중 가장 오른쪽에 있는 기둥을 만나면 break
			// 오른쪽부터 시작했기 때문에 가장 먼저 만나는 높은 기둥이 가장 오른쪽에 있음
			if(arr[i]==max) break;
		}

		System.out.println(sum);
		
	}

}

결과

 

#자바 #java #boj #백준 #알고리즘