✉️문제
https://www.acmicpc.net/problem/14719
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
📝 접근
- 왼쪽에 있는 기둥의 최대값(LM)과 오른쪽에 있는 기둥의 최대값(RM)을 구한다.
- LM과 RM의 최소값을 구한다.
- 최소값 - 현재 인덱스의 높이
🗝 문제풀이
public class Q14719_B {
static int[] heights;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int h = sc.nextInt();
int w = sc.nextInt();
heights = new int[w];
for(int i = 0; i < w; i++) {
heights[i] = sc.nextInt();
}
int sum = 0;
for(int i = 1; i < w - 1; i++) {
int currentHeight = heights[i];
// 왼쪽에서 가장 긴 기둥
int LM = 0;
for(int j = 0; j <= i; j++) { // 이거를 포함 안하면 안됨.
LM = Math.max(LM, heights[j]);
}
// 오른쪽에서 가장 긴 기둥
int RM = 0;
for(int j = i; j < w ; j++) {
RM = Math.max(RM, heights[j]);
}
sum += Math.min(LM, RM) - currentHeight;
}
if(sum < 0) sum = 0;
System.out.println(sum);
}
}