알고리즘(BOJ)/Gold

백준 - 빗물 14719

ch.0 2023. 2. 5. 21:44


문제 분석

문제 이해도 쉽고 풀이과정을 생각하는게 재밌는 문제였다.

첫열과 마지막열에는 빗물이 찰 수 없으니 넘겨주고 두번째 열부터 왼쪽과 오른쪽에 자신보다 큰 벽이 있는지 확인했다.

일부러 2차배열을 선언하지 않고 풀려고 노력했다.

 

 

 

 

전체소스

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());

		int[] array = new int[y];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < y; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		int L = 0, R = 0;
		boolean L_check = false, R_check = false;
		int count = 0, result=0;

		for (int i = 1; i < y - 1; i++) {
			for (int j = array[i] + 1; j <= x; j++) {
				L=i-1;
				R=i+1;
				while (L >= 0) {
					if (j <= array[L])
						L_check = true;

					L--;
				}
				while (R < y) {
					if (j <= array[R])
						R_check = true;

					R++;
				}
				if (L_check == true && R_check==true) {
					count++;
				}
				L_check = false;
				R_check = false;
				
			}
			result += count;
			count=0;
			
		}System.out.println(result);

	}

}

while문으로 왼쪽과 오른쪽에 벽이 있는지 확인했다.

 

* j의 범위를 x보다 작게 해서 4004 의 벽일경우 3까지밖에 차지않았었다.

 

 

 


문제

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

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

입력

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

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

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

출력

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

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

예제 입력 1 복사

4 4
3 0 1 4

예제 출력 1 복사

5

예제 입력 2 복사

4 8
3 1 2 3 4 1 1 2

예제 출력 2 복사

5

예제 입력 3 복사

3 5
0 0 0 2 0

예제 출력 3 복사

0

힌트

힌트 1:

힌트 2:

힌트 3: