[백준] G5 14719 빗물 (java)

https://www.acmicpc.net/problem/14719

14719번: 빗물

 

풀이

 

1) 입력된 지형을 map[] 배열에 담는다. 이때 가장 높은 지점의 높이와 인덱스를 저장해 놓는다.

2) 왼쪽 끝에서 max 인덱스 까지 검사한다.

2-1) 시작 지점의 높이보다 작을 경우 빗물이 고이는 경우이다. start - map[i] 만큼 빗물이 고인다.

2-2) 시작 지점의 높이보다 클 경우 시작지점을 초기화 해준다.

3) 오른쪽도 왼쪽과 같은 방식으로 진행한다.

4) 저장된 빗물을 출력한다.

 

주의사항

 

1) 만약 가장 높은 지점이 2개 이상일경우 어떻게 할까 고민했지만 그 중 하나만 알고있어도 전혀 문제가 없다.

 

package com.baekJoon;

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

public class BJ_G5_14719_빗물 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int H,W,map[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		H = Integer.parseInt(tokens.nextToken());
		W = Integer.parseInt(tokens.nextToken());
		map = new int[W];
		tokens = new StringTokenizer(input.readLine());
		int max = Integer.MIN_VALUE;
		int maxIndex = 0;
		for(int i=0; i<W; i++) {
			map[i] = Integer.parseInt(tokens.nextToken());
			if(max < map[i]) {
				max = map[i];
				maxIndex = i;
			}
		}
		int sum = 0;
		// 왼쪽 끝에서 max 까지
		int start = map[0];
		for(int i=0; i<maxIndex; i++) {
			if(map[i] < start) {
				sum += start - map[i];
			}else {
				start = map[i];
			}
		}
		// 오른쪽 끝에서 정상까지
		start = map[W-1];
		for(int i=W-1; i>maxIndex; i--) {
			if(map[i] < start) {
				sum += start - map[i];
			}else {
				start = map[i];
			}
		}
		System.out.println(sum);
	}

	static String src =

			"4 3\r\n"
			+ "3 1 2";
}

 

후기

 

 골드 난이도 치고는 정말 쉬운 문제였다.