문제

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

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

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

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)
두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.
따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

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

예제

---

내 풀이

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	// 1 ≤ H, W ≤ 500
	int h, w;
	cin >> h >> w;

	// 2차원 배열 동적 할당 
	int** m = new int* [h]; // h행
	for (int i = 0; i < h; i++) {
		m[i] = new int[w] {}; // w열 (0으로 초기화)
	}

	for (int c = 0; c < w; c++) {
		int tmp;
		cin >> tmp;

		// 열은 고정, 행은 아래에서 위로 이동
		int r = h - 1;
		while (tmp--) { // tmp 개수만큼 1로 채우기 
			m[r][c] = 1; 
			r--;
		}
	}

	int sum = 0, cur = 0;
	for (int i = 0; i < h; i++) {
		int cnt = 0; // 각 행마다 빗물이 고일 수 있는 칸의 수 카운팅 
		 
		for (int j = 0; j < w; j++) {

			if (m[i][j] == 1) {
				int partialCnt = 0; // 1과 1 사이에 있는 0의 개수 카운팅 

				// 1이 등장한 바로 다음 열부터 검사 
				cur = j + 1; 
				while (m[i][cur] == 0 && cur < w) {
					partialCnt++; // 0의 개수 증가
					cur++; // 커서 이동 
				}

				if (cur >= w) { // 인덱스 범위를 넘은 경우 
					if (m[i][cur - 1] == 1) { // 마지막 열이 1이어야 
						cnt += partialCnt; // 빗물이 고일 수 있음.
					}
				}
				else {
					// cur < w에서 while 루프가 종료되면, 1이 다시 등장했다는 것! 
					cnt += partialCnt;
				}

				// 검사를 다시 시작할 인덱스로 갱신 
				j = cur - 1; // j는 곧 ++되기 때문에 cur가 아니라 cur-1로 갱신해야 함.
			}
		}

		//cout << i << "행: " << cnt << "\n";
		sum += cnt;
	}

	cout << sum << endl;

	return 0;
}

다른 풀이

참고: https://yabmoons.tistory.com/645

#include <iostream>
#include <vector>
using namespace std;

int h, w, answer;
int height[501];

int main()
{
	cin >> h >> w;

	// 각 열의 높이 입력 받기 
	for(int i = 1; i <= w; i++){
		cin >> height[i];
	}

	// 2열 ~ (w-1)열 검사 
	for(int i = 2; i < w; i++){
		int left, right;
		left = right = 0;

		// 현재 열의 왼쪽에서 최대 높이 구하기
		for(int j = 1; j < i; j++){
			left = max(left, height[j]);
		}

		// 현재 열의 오른쪽에서 최대 높이 구하기 
		for(int j = i + 1; j <= w; j++){
			right = max(right, height[j]);
		}

		// 둘 중에 더 낮은 높이와 현재 열의 높이의 차이만큼 빗물이 고인다.
		int result = min(left, right) - height[i];
		if(result >= 0) answer += result;
	}

	cout << answer << endl;
	
	return 0;
}