[문제풀이] 빗물

업데이트:

문제 링크 : 빗물

풀이 시간 : 20분

1. 문제 풀이

0번째를 최대로 놓고 시작하면서 채울 수 있는 양 계산

높이를 비교하면서 최대 높이보다 크거나 같으면 빗물의 양을 구하고 최대 높이를 변경

현재 최대 높이가 마지막까지 유지되면 빗물을 받지 못하기 때문에 마지막부터 오른쪽 방향으로 거꾸로 진행

2. 소스 코드

    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int sum = 0;
		st.nextToken();
		int W = Integer.parseInt(st.nextToken());
		int[] arr = new int[W];
		st = new StringTokenizer(br.readLine());
		
		arr[0] = Integer.parseInt(st.nextToken());
		int max = arr[0];
		int pivot = 0;
		boolean flag = false;
		for (int i = 1; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			// 왼쪽부터 담길 수 있는 높이
			if (max <= arr[i]) {
				for (int j = pivot; j < i; j++) {
					sum += max - arr[j];
				}
				max = arr[i];
				pivot = i;
				flag = true;
			} else {
				flag = false;
			}
		}
		// 현재 최대 높이로 담지 못할 경우, 제일 오른쪽이 최대값보다 낮을 경우
		if (!flag) {
			max = arr[arr.length - 1];
			int end = pivot;
			pivot = arr.length - 1;
			// 오른쪽 끝 부터 위에 작업 반복
			for (int i = arr.length - 2; i >= end; i--) {
				if (max <= arr[i]) {
					for (int j = pivot; j > i; j--) {
						sum += (max - arr[j]);
					}
					max = arr[i];
					pivot = i;
				}
			}
		}
		System.out.println(sum);

3. 후기

간단하게 최대 높이를 바꿔주면서 받을 수 있는 빗물을 더해주면 되는 문제입니다.

다만 왼쪽부터 진행하면서 생긴 최대 높이가 마지막까지 갔을 때 마지막 높이가 작으면 빗물을 담을 수 없다는 점을 생각해야 합니다.

그래서 마지막부터 전 최대 높이 인덱스까지 거꾸로 진행을 한번 해야합니다.

참고