[백준] 빗물

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

1662번: 압축

 

아직 부족하다고 많이 느끼게 해준 문제...

간단해보이지만 바로 로직이 생각나지 않았다.

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int H, W;
int answer;
vector<int> v;

void input() {
	cin >> H >> W;
	for (int i = 0; i < W; i++) {
		int n;
		cin >> n;
		v.push_back(n);
	}
}

void solve() {
	for (int i = 1; i < W-1; i++) {
		int left = 0;
		int right = 0;

		//왼쪽 최대값.
		for (int j = 0; j < i; j++) {
			left = max(left, v[j]);
		}
		//오른쪽 최대값
		for (int j = i + 1; j < W; j++) {
			right = max(right, v[j]);
		}
		int rain = min(left, right) - v[i];
		if (rain < 0) rain = 0;
		answer += rain;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);

	input();
	solve();

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