[백준-14719] 빗물

이 문제는 백준의 골드 5레벨 문제이다.

 

이 곳을 클릭하면 문제 페이지로 이동합니다.

 

어제부터 어떤 분이 정리해두신 코딩테스트 대비를 위한 문제 리스트를 풀고 있는데, 레벨별로 정말정말 정리를 잘 해두셨다. 이 문제도 그 문제 중 하나였다.

 

시뮬레이션 기본 문제라고 하셨는데, 사실 골드 5 레벨 치고는 좀 쉬웠던 것 같다.

문제 푸는 시간보다 블로그 포스팅이 더 오래걸릴 수도 있겠다는 생각이 들 정도로..?

 

이 문제는 빗물이 쌓인 부분들을 계산하면 되는 문제인데,

1) 2차원 배열을 만들어서 땅이 있는 부분이라면 1을 저장해준다.

2) 2차원 배열을 처음부터 돌면서

  2-1) 이번에 도착한 곳이 땅인데 지난번에 도착한 곳도 땅이라면 temp = 0

  2-2) 이번에 도착한 곳이 빈 공간인데 지난번에 땅이였다면 카운팅 스타트!

  2-3) 이번에 도착한 곳이 빈 공간인데 물이 고이는 중이라면 계속 카운트

  2-4) 물이 고이다가 새로운 땅을 만나면 지금까지 고인 물들 총 합에 더해주기

 

2번과정을 배열 처음부터 끝까지 반복해주면 답이 나온다.

 

import java.util.Scanner;

public class 빗물_14719 {
	static int H,W;
	static int[][] map;
	static boolean[][] visited;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		H = sc.nextInt();
		W = sc.nextInt();
		map = new int[H][W];
		
		for(int i=0; i<W; i++){
			int h = sc.nextInt();
			if(h>0) {
				for(int j=0; j<h; j++) {
					map[j][i] = 1;
				}
			}
		}
		
		int sum = 0;
		for(int i=0; i<H; i++) {
			int temp = 0;
			for(int j=1; j<W; j++) {
				if(map[i][j-1] == 1 && map[i][j] == 1)
					temp = 0;
				else if(temp == 0 && map[i][j-1] == 1) {
					temp++;
				}else if(temp != 0 && map[i][j] == 0) {
					temp++;
				}else if(temp != 0 && map[i][j] == 1) {
					sum += temp;
					temp = 0;
				}
			}
		}
		System.out.println(sum);
	}
}

 

사실 숫자가 0이랑 1밖에 안 쓰여서 map을 int형이 아닌 boolean형으로 만들어도 될 것 같다.

그러면 메모리 사용을 줄일 수 있을 것 같다.