[백준 14719] 빗물

문제

www.acmicpc.net/problem/14719

14719번: 빗물

 

풀이

1. 어떤 칸에 빗물이 채워지는 조건에 대해서 생각해볼 때, 그 칸을 제외한 (좌측의 최대 높이, 우측의 최대 높이) 둘 중 작은 높이에서 어떤 칸의 높이를 뺀 만큼 채워진다는 걸 알 수 있습니다. (물론 물이 채워져야 하므로 좌측의 최대 높이, 우측의 최대 높이는 어떤 칸의 높이보다 높아야 합니다.)

 

2.  i칸을 제외한 i칸 좌측의 최대 높이를 $pre[i]$, 우측의 최대높이를 $suf[i]$라고 할 때, 그 의미대로 아래와 같이 표현할 수 있습니다. 

 

$pre[i] = max(pre[i - 1], v[i - 1]) (단, 1<= i < w - 1)$

$suf[i] = max(suf[i + 1], v[i + 1]) (단, 1 <= i < w - 1)$

 

코드

#include <bits/stdc++.h>
using namespace std;

int h, w, ans;
vector<int> v, pre, suf;

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> h >> w;
	v.resize(w), pre.resize(w), suf.resize(w);
	for (int i = 0; i < w; i++) cin >> v[i];

	pre[0] = v[0];
	for (int i = 1; i < w - 1; i++)
		pre[i] = max(pre[i - 1], v[i - 1]);

	suf[w - 1] = v[w - 1];
	for (int i = w - 2; i >= 1; i--)
		suf[i] = max(suf[i + 1], v[i + 1]);

	for (int i = 1; i < w - 1; i++)
		if (pre[i] > v[i] && suf[i] > v[i])
			ans += min(pre[i], suf[i]) - v[i];
	cout << ans;
}