백준 14719번 : 빗물

 문제

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

14719번: 빗물

14719 빗물

 

 구현 방법

리스트에 각 층이 몇 층인지 넣어 준 다음 제일 아래층부터 한 층씩 계산해주었습니다.

1. 현재 계산 중인 층 < 해당 열의 층수 == 벽이다!! -> isWall은 true
2. 현재 계산 중인 층 >= 해당 열의 층수이고 isWall이 true(이미 앞에 벽이 있었다면) == 물이 고일 수 있으므로 cnt++
3. 현재 계산 중인 층 < 해당 열의 층수 == 벽인데 isWall이 true(이미 앞에 벽이 있었다면) == 고인 물 끝이므로 totalCnt에 더해주고 cnt는 초기화

 

처음에 1%에서 틀렸습니다가 떠서 반례를 구해보았습니다.

 

totalCnt를 더하고 cnt를 초기화 해주니 층을 훑을때마다 cnt 초기화는 필요 없다고 생각해서 생략했습니다.
하지만 위 예제의 2층 처럼 앞에 벽이 있고 범위를 벗어나 그대로 끝이 났다면 cnt 초기화는 필요했습니다.
따라서 층을 훑을때마다 cnt를 초기화 해주었고 맞을 수 있었습니다!!

 

 구현 코드

package BOJ.Gold;

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

public class BOJ14719_빗물 {
	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());
		List<Integer> list = new ArrayList<>();
		st = new StringTokenizer(br.readLine());
		int MAX = Integer.MIN_VALUE;
		for (int w=0;w<W;w++) {
			list.add(Integer.parseInt(st.nextToken()));
			if (MAX < list.get(w)) MAX = list.get(w);
		}
		int cnt, totalCnt = 0;
		boolean isWall;
		
		for (int h=0;h<H;h++) {
			cnt = 0; isWall = false; // 초기화
			if (h>MAX) break; // 현재 높이가 가장 높은 벽보다 높아지면 멈춰주기
			for (int w=0;w<W;w++) {
				int now = list.get(w); 
				if (now>h && !isWall) isWall = true; // 현재 높이보다 값이 크면 -> 벽이므로 해당 높이에 물 고일 수 있음
				else if (now<=h && isWall) cnt++; // 현재 높이보다 값이 작고 앞에 이미 벽이 있었다면 cnt++
				else if (now>h && isWall) { // 앞에 벽이 있었고 또 다른 벽이 나타났다면
					totalCnt+=cnt; // 총 빗물 개수 구해주기
					cnt = 0; // 초기화
				}
			}
		}
		
		System.out.println(totalCnt);
	}
}

 

정답!