[백준/JAVA] 14719번: 빗물

🔺 문제

14719번: 빗물

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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());   // 가로
        
        int arr[] = new int[W];
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < W ; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); 
        }
        
        // 인덱스마다 모이는 빗물 계산 (첫번째, 마지막 제외)
        int result = 0;
        for(int i = 1 ; i < W - 1 ; i++) {
            int leftMax = 0;    // 왼쪽 벽 최대 높이
            int rightMax = 0;   // 오른쪽 벽 최대 높이
            
            // 왼쪽 최대벽 높이 탐색
            for(int j = 0 ; j < i ; j++) {
                leftMax = Math.max(leftMax, arr[j]);
            }
            
            // 오른쪽 최대벽 높이 탐색
            for(int j = i + 1 ; j < W ; j++) {
                rightMax = Math.max(rightMax, arr[j]);
            }
            
            // 현재 벽보다 높은 벽이 양쪽에 있을 때
            // 더 낮은 건물 기준으로 빗물이 현재 인덱스에 모임
            if(arr[i] < leftMax && arr[i] < rightMax)
                result += (Math.min(leftMax, rightMax) - arr[i]);
        }
        
        System.out.println(result);
    }
}

✅ 해결 아이디어
- 양쪽 가장 자리는 물을 채울 수 없음.
- 현재 벽 위치 기준 왼쪽 최대벽, 오른쪽 최대벽 높이 탐색
- 현재 벽보다 높은 벽들이 양쪽에 있을 때 , 둘 중 더 낮은 건물 높이 - 현재 위치 높이만큼 빗물이 모임

---

🔺 다른 풀이들

- 다른 답들은 거의 비슷한데 조금 달라서,,,

[백준 14719] 빗물 (JAVA)

 

 

- 과정 보고 무슨 말하는지 좀 이해가 갔다.

백준 14719 자바 - 빗물 (BOJ 14719 JAVA)

---

💬 느낀 점

2차원 배열 사용하고 막 그럴까 생각하다가..

그것이 아님을 깨닫고...

디버깅하고 왜 해결방식이 이런지 이해할 수 있었다...

 

돌아가라 머리머리...

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

- 1차 이해...

[알고리즘] 백준 14719 빗물 자바

 

 

- 과정 설명 굿... 덕분에 이해했습니다..ㅠ

[BAEKJOON_14719 - JAVA] 빗물