[백준] 빗물 - 14719 : Java

문제 링크

성능 요약

메모리: 14412 KB, 시간: 144 ms

분류

구현, 시뮬레이션

문제 설명

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

 

---

🧐 어떻게 풀까

시작 블록을 정하고 시작 블록보고 큰 블록이 나타나면 구역으로 지정하여 빗물을 구하는 과정을 반복하면 되지 않을까?

그림을 다시보니 큰 블록 다음 작은 블록이 나타나도 빗물이 고인다.. 어떻게 해야할까 -> 인터넷!

 

풀이

• 물이 고일 수 있을 때 -> 양 옆 블록이 현재 블록보다 클 때
• 어느 정도 고일 수 있나? -> MIN(왼쪽 블록 중 가장 큰 길이, 오른쪽 블록 중 가장 큰 길이)
• 첫블록과 마지막 블록은 물이 고일 수 없다.

위 조건을 만족하도록 코드를 짠다.

import java.io.*;
import java.util.*;

public class Main {

	public static BufferedWriter bw;
	public static BufferedReader br;



	public static void main(String[] args) throws Exception {

		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());

		int map [] = new int[W];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<W; i++) {
			map[i] = Integer.parseInt(st.nextToken());
		}

		int sum = 0;
		for(int i=1; i<W-1; i++) {
			int maxL =0;
			int maxR = 0;
			for(int j=0; j<i; j++) {
				maxL = Math.max(maxL, map[j]);
			}
			for(int k=i+1; k<W; k++) {
				maxR = Math.max(maxR, map[k]);
			}
			int max = Math.min(maxL, maxR);

			if(map[i] < max)
				sum += max - map[i];
		}

		System.out.println(sum);
	}


}

 

 

헤맨 점

당연히 O(n²) 알고리즘은 안될 줄 알고 생각하지 않았다. 하지만 문제의 입력값은 최대 500이므로 O(n²) 으로 풀어도 1초 안에 넉넉하게 풀 수 있다. 구현 문제는 생각보다 시간을 크게 제한하지 않는 문제도 있는 것 같다. 앞으로 더 입력 범위에 따른 적절한 알고리즘을 생각해봐야겠다.