[백준] 14719번 빗물

14719번: 빗물
(1:00)

• 고이는 빗물의 총량은 얼마일까?
  • 빗물이 전혀 고이지 않을 경우 0을 출력한다.
• h → row : 1이상 500이하
• w → column : 1이상 500이하
• 각 블록의 높이는 0이상 h 이하
  • 근데 이차원 세계의 바닥은 항상 막혀있다.

문제 이해

• 빗물이 고이기 위해서는 움푹 파인 곳이 필요하다.

  • 움푹 파인 곳이라는 것은 이런식으로 감싸지는 곳이다.

    ◼◻◻◼
    ◼◼◻◼  
    ◼◼◼◼
    //3

  • 그리고 예시를 통해

    0 0 0 2 0 
    ◻◻◻◻◻
    ◻◻◻◼◻  
    ◻◻◻◼◻
    //0
    

    이런 경우는 고인 곳이 없다는 것이니,막히지 않았다면
    고일 수 없음을 의미함을 알 수 있다.

    즉 아래의 경우도 정답은 0이다

    ◼◻◻◻
    ◼◼◻◻  
    ◼◼◼◻
    

풀이 생각

여전히 잘 못한다는 것이 느껴졌다.

• 완전탐색?

• h(cur-1) < h(cur) 인 때 , cur의 좌측에서의 고인 물의 높이를 구할 수 있다.

  ◼◻◻◻◼
  ◼◼◻◻◼ 
  ◼◼◼◻◼
  
  ◼◻◻◻◻◻
  ◼◼◻◻◻◼ 
  ◼◼◻◼◻◼
  ◼◼◻◼◻◼
  
  4 6
  4 3 0 2 0 3
  
  ◼◻◻◻◻◻
  ◼◼◼◼◼◼ 
  ◼◼◼◼◼◼
  ◼◼◼◼◼◼
  4 6
  4 3 3 3 3 3
  // 그런데 이런 경우도 풀기 위하여
  // 이미 계산한 곳은 칸을 채우도록 한다 
  ◼◻◻◻◻◻
  ◼◻◻◻◻◻ 
  ◼◼◻◻◻◻
  ◼◼◻◻◻◼
  4 6
  4 2 0 0 0 1

  • cur-1부터 pre라고 지칭하며 pre를 decreasing하면서, 처음으로 h(cur)보다 크거나 같은 높이가 나오는 순간 or h(pre-1)<h(pre) or pre==0 인 경우를 찾는다.
  • 이렇게 찾은 pre를 left bound로 한다.
  • h(left)와 h(cur) 중 minimum 인 곳 만큼 그 사이 공간이 빗물로 채워진다 .
  • 이렇게 할 경우, 현재 cur 보다 더 큰 cur이 나오는 경우에는, 이렇게 채워진 빗물 위로도 채워질 수가 있다.

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

public class Main {
    public static int tr,tc;
    public static int[] h = new int[500];
    public static int acc=0;
    public static void solve(){
        //boolean reserv=false;
        // for 문 조건상 자동으로, tc가 1인 경우에는 0이 된다.
        for(int i=1;i<tc;i++) {
            if (h[i] > h[i - 1] ) {
                //빗물을 구한다.
                accum(i);
            }
        }
    }
    public static void accum(int cur){
        int pre = cur-1;
        int left =0;

        while(true){
						if(pre==0||h[cur]<=h[pre] ||h[pre-1]<h[pre])break;           
						pre--;
        }
        // cur을 right bound, pre를 left bound라고 한다.
        // 이 둘 중 작은 값으로, 빗물이 채워지고 -> 빗물을 채운다.
        left = pre;
        int limit = Math.min(h[cur],h[left]);
        for(pre=left+1;pre<cur;pre++) {
            acc += (limit - h[pre]);
            //
            h[pre] = limit;
        }
    }
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        tr = Integer.parseInt(st.nextToken());
        tc = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<tc;i++){
            h[i] = Integer.parseInt(st.nextToken());
        }
    }

    public static void main(String[] args) throws IOException {
        Setting();
        solve();
        System.out.println(acc);
    }
}

다른 사람 풀이

• 풀면서 내 풀이에 혼란이 왔고 깔끔하지 못하다 느꼈다. 한 번에 감이 오는 방법이 없었다. 그래서 다른 사람 풀이도 보았다.
• 다른 사람 풀이를 보니 깔끔하다.
• 💥cur을 기준으로, 왼쪽 오른쪽을 검색 → 왼쪽기준 중 [ 가장 큰 놈 (index = left) ] 과 오른쪽기준 중 [ 가장 큰놈 (index = right)] 을 구한다
  • 그리고는 그 둘 중 작은 값을 구한다. (limit = Math.min(h(left),h(right))
  • 현재 내 위치에서 채울 수 있는 빗물 : limit - h(cur) 이다.
  • 💥 i는 어떤 두 개 사이에 있는 것이어야 한다 → 맨 첫 번째, 맨 뒤의 것은 cur 의 대상에서 제외한다.