백준 14719 빗물

문제 바로가기

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

알고리즘 힌트를 봤더니 구현, 시뮬레이션이라고 적혀있다. 그렇다 뭐든 써서 풀기만하면 되는것이다.

처음 생각한 방법은, 그림과 같은 이차원 배열을 다 탐색해 보면서 블록과 블록 사이에 있는 흰공간의 개수만 세주자 였다.

1. 한 행을 을 탐색할 때, 검정색 블록이 나오면 그 다음부터 개수를 세주기

2. 검정 블록이 연속으로 나오는 경우에 대처

위 두 가지를 생각하면서 코드를 작성해보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_14719_빗물 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		boolean flag = false; //흰 블록을 세기위한 스위치 true면 셀 수 있다.
		int[] arr = new int[W];
		st = new StringTokenizer(br.readLine(), " ");
		int maxH = 0;
		for (int i = 0; i < W; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			maxH = Math.max(maxH, arr[i]);
			//주어진 블록들의 높이가 H보다 낮을수도 있으므로 최대 높이 블록 저장
		}
		int sum = 0;
        	//최대 높이 블록의 행 부터 검사 시작
		for (int i = H - maxH; i < H; i++) {
			int cnt = 0;
			flag = false;
            		for (int j = 0; j < W; j++) {
                    		//검정색 블록이라면 흰 블록 세야하므로 flag = true;
				//무조건 sum에 더해주고 nt는 0으로 초기화 
				if (i >= (H - arr[j])) {
					flag = true;
					sum += cnt;
					cnt = 0;
					continue;
				}
                		//flag가 true면 흰 블록 개수를 셀 수 있다.
				if (flag) 
					cnt++;
			}
		}
		System.out.println(sum);
	}
}

굉장히 단순한 해법.. 그리고 최대 높이의 블록의 행 인덱스 부터 시작하므로 최대한 시간을 아낄 수 있다. 속도도 136ms으로 생각보다 빠르게 나왔다.

두 번째로 생각한 방법은, 가장 높은 블록의 위치(maxH)를 기준으로 양쪽에서 maxH까지 탐색해 주면서 흰 공간을 계산하는것이다.

물이 고일 수 있는지만 체크해주면 된다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_14719_빗물2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int[] arr = new int[W];
		st = new StringTokenizer(br.readLine(), " ");
		int maxH = 0;
		int posi = 0;
		for (int i = 0; i < W; i++) {
			int s = Integer.parseInt(st.nextToken());
			if (maxH < s) {
				maxH = s;
				posi = i; // 가장 긴 블록의 길이와, 위치 저장
			}
            		arr[i] = s;
		}
		int sum = 0;
		int a = arr[0];//기준을 정해줌 
		int b = arr[W - 1];
		for (int i = 1; i < posi; i++) {
			if (a > arr[i]) {
            		// 기준보다 작으면 물이 고일 수 있으므로 값을 더해준다
				sum += a - arr[i];
			} else {
            		// 기준보다 크면 물이 고일 수 없으므로 기준을 갱신
				a = arr[i];
			}
		}
		for (int i = W - 1; i > posi; i--) {
			if (b > arr[i]) {
				sum += b - arr[i];
			} else {
				b = arr[i];
			}
		}
		System.out.println(sum);
	}
}

이 방식이 132ms로 조금 더 빨랐다.
코테 통과하려면 멀었다~~ 분발하자 피나코