[Baekjoon] 14719_빗물

Gold V

문제(출처: https://www.acmicpc.net/problem/14719)

---

< 빗물 >

 

문제 풀이

 

그림과 같이 블록을 순환하며 최댓값 두 개를 찾아야 빗물이 고이는 구간을 찾을 수 있다.

젤 첫 번째 값을 start로 지정하고 start보다 큰 값이나 start보다 작거나 같은 값 중 최댓값을 end로 지정한다.

그 후 start와 end 사이에 빗물이 고이는 양을 구한다.

 

위와 같은 방식으로 가로를 다 순환할 때까지 반복하면 빗물이 고이는 총량을 구할 수 있다.

 

 

 

 my solution (Java)

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

public class _14719_ { // 빗물

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int h = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());

		int arr[] = new int[w];
		int result = 0;

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < w; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int num = 0, idx = 0;
		while (idx < w - 1) {
			int start = arr[num];
			int end = arr[num + 1];
			for (int i = num + 1; i < w; i++) {
				if (end <= arr[i]) {
					end = arr[i];
					idx = i;
				}
				if (start < arr[i]) {
					end = arr[i];
					idx = i;
					break;
				}
			}
			int min_val = start;
			if (start > end)
				min_val = end;

			for (int i = num; i < idx; i++) {
				if (min_val - arr[i] > 0) {
					result += min_val - arr[i];
				}
			}
			num = idx;
		}
		System.out.println(result);
	}
}

 

Main

- 세로 길이(h), 가로길이(w) 입력

- arr: 블록이 쌓인 높이 저장

- 블록을 순환하며 앞에서부터의 최댓값(start)과 그 이후로부터의 최댓값(end)을 찾아 블록이 고일 수 있는 구간 찾기 ->  start와 end 중 최솟값을 찾기 -> 그 사이 구간에 고이는 빗물의 양 구하기

 

---

생각🤔

 

---