[백준] 14719 빗물

14719번: 빗물 (acmicpc.net)

14719번: 빗물

 

문제

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

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

입력

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

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

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

 

 

내풀이

 

처음 맵 정보를 받는 즉시 수학적으로 뭔가 계산하면 될 것 같은 느낌이 들어 생각을 하다가 마땅한 것이 생각이 나지 않아 빗물이 고이려면 블록이 양옆으로 가둬줘야 된다는 것에 집중했다.

어떻게 해결했냐면, 맵 정보를 boolean 이차원 배열로 받고 블록을 true 로 받고 빈공간을 false 로 그리고 한 행씩 true 사이에 갇힌 false 의 갯수를 세주어 합치는 방법으로 해결하였다.

 

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

public class Main{
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static String src="3 5\n" +
			"0 0 0 2 0";

	public static void main(String arg[]) throws IOException {
		//input= new BufferedReader(new InputStreamReader(System.in));
		input= new BufferedReader(new StringReader(src));

		int H, W, result = 0;

		StringTokenizer str = new StringTokenizer(input.readLine());

		H = Integer.parseInt(str.nextToken());
		W = Integer.parseInt(str.nextToken());

		str = new StringTokenizer(input.readLine());
		boolean[][] Map = new boolean[H][W];

		for (int j = 0; j < W; j++) {
			int curH = Integer.parseInt(str.nextToken());
			for (int i = H - 1; i > H - curH - 1; i--) {
				Map[i][j] = true;
			}
		}

		int count;
		boolean flag; //이전에 true 가 있었는지
		//true 사이의 false 갯수 세어줄 것임
		for (int i = H - 1; i >= 0; i--) {
			flag = false;
			count = 0;
			for (int j = 0; j < W; j++) {
				//true 이면 다음 true 올때까지의 false 세어줌
				//이전에 세던 것이 있으면 count 결과에 더해줌
				if (Map[i][j]) {
					flag = true;
					//System.out.println(i+" "+ j+" "+count);
					result += count;
					count = 0;
				}
				if (!Map[i][j] && flag) {
					count++;
				}
			}

		}
		System.out.println(result);
	}

}