Baekjoon #14719 빗물

빗물

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

14719번: 빗물

 

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다. 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

 

출력

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

---

최근에 푼 다른 문제들보다 간단한 문제였다. (왜 골드인지는 모르겠다... 실버가 너무 어렵다!!!!...ㅠ)

변수를 최소한으로 하려고 애썼다.

 

처음에는 2차원 배열로 하려고 하다가 1차원배열로 map을 그릴 수 있도록 하였다.

---

풀이

빗물은 수평적(horizontal)하게 쌓이게 된다. 여기서 조건은 빗물이 쌓일려면 양옆에 (그림에서 본다면) 검정색 타일이 필요하다는 것이다. 바닥은 항상 막혀있다고 했으므로 양 옆에 타일이 있는지만 확인하면 된다.

row에 대한 빗물의 양 계산

2차원 맵을 가지고 탐색하여 해결할 수도 있겠지만, 굳이 2차원 배열을 만들 필요가 없다.

 

주어진 1차원배열의 값으로 한칸씩 칼럼(열)에 쌓는다고 생각하면 된다.

 

 

 

문제에서 주어진 이미지와 상하가 뒤바뀌기는 하지만 답이 달라지지는 않는다.

 

1차원 배열의 column에 대한 값에 row를 빼준 값이 0보다 작거나 같으면 그 부분은 빗물을 받을 수 있는 검정색 타일이 아니다.

 

이로써, 전체 순회방법을 생각하였다. 남은 것은 한 row에 빗물을 받을 수 있는 부분이 여러개 나올 수 있다는 점을 생각해야한다.

 

end column - start column - 1 = 빗물의 양

 

첫번 째 나온 검정색 타일은 계산 시 항상 start column이 될 수 있지만, 두 번째 부터의 검정색 타일은 start column 뿐만 아니라 end column도 될 수 있다. (빗물을 양 옆으로 받을 수 있다.)

 

따라서 간단하게 수도 코드를 작성하게 되면

check = -1 // default value for (row : 열):     for (column : 행):         // start / end 체크         if (check != -1 && arr[column] - row > 0):             answer += (column - check - 1)             check = column // check 위치를 column으로 바꾸기         else if (arr[column] - row > 0): // start 만 체크             check = column     check = -1 // 한 줄(row)가 끝났으면 check 초기화

---

전체 코드

/*
* 빗물
* https://www.acmicpc.net/problem/14719
* */

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

public class P14719 {
    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[] ws = new int[w];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i=0; i<ws.length; i++) {
            ws[i] = Integer.parseInt(st.nextToken());
        }

        int amount = 0;
        int check = -1;

        for (int r=0; r<h; r++) {
            for (int c=0; c<w; c++) {
                if (check != -1 && ws[c] - r > 0) {
                    amount += ( c - check - 1);
                    check = c;
                }
                else if (ws[c] - r > 0) {
                    check = c;
                }
            }
            check = -1;
        }

        System.out.println(amount);
    }
}