[백준] 14719번 빗물

www.acmicpc.net/problem/14719

14719번: 빗물

문제 설명 : 빗물의 총량 구하기 문제 풀이 :  arr 배열은 블록이 쌓인 높이를 담고 있다. 빗물이 고이는 조건(양 옆이 자신 보다 클 경우)을 만족시키기 위해, arr 배열을 반복해서 돌면서 해당 인덱스의 왼쪽에서 가장 큰 숫자를 left에 오른쪽에서 가장 큰 숫자를 right에 저장한다. 이후 빗물이 고이는 양(두개의 블록 중 작은 블록까지 빗물이 채워짐)을 구하기 위해 left 와 right 중 작은 숫자를 구한다. 최종적으로 작은 블록 크기에서 해당 인덱스 크기를 빼면 빗물이 고인 용량이 나오고 answer 변수에 계속 갱신해준다. 주의할 점 : left right 변수 초기화

import java.util.Scanner;

public class Main{
	static int H,W;
	static int[] arr;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		H = sc.nextInt();
		W = sc.nextInt();
		arr = new int[W];
		int answer = 0;
		
		for (int i = 0; i < W; i++) {
			arr[i] = sc.nextInt();
		}
		
		
		for (int i = 1; i < W; i++) {
			int left=-1, right=-1, min = 0, result =0;

			//현재 인덱스에서 왼쪽에서 가장 큰 숫자구하기
			for (int j = i; j >= 0; j--) left = Math.max(arr[j], left);
            //현재 인덱스에서 오른쪽에서 가장 큰 숫자 구하기
			for (int j = i; j < W; j++)	right = Math.max(arr[j], right);
			
            //둘 중 작은 숫자 - 현재 인덱스 숫자-> 결과에 더하기
			min = Math.min(left, right);
			result = min - arr[i];
			answer += result;
		}
				
		System.out.println(answer);
	}
}