[C++] 백준 14719 빗물

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

14719번: 빗물

 

문제 해결

• 높이의 기준을 잡아야 한다.
• 가장 끝 왼쪽과 오른쪽이 모두 가장 높은 길이이면 쉽제 $\sum (min(*가장 왼쪽 높이, *가장 오른쪽 높이)-i)*(w-2)$ ($i=1,2,3...$)라는 것을 알 수 있다
• 여기서 관점을 바꾸어 $i$를 기준으로 생각을 해보면 $i$보다 왼쪽,오른쪽 모든 방향에 블록의 높이중 $i$번째 높이보다 큰 것이 있다면 $min(왼쪽 높이중 가장 큰 것, 오른쪽 높이중 가장 큰 것)-height[i]$만큼 정답에 더해야함을 알 수 있다. 만약 아니라면 그냥 넘어가면 된다.
• 관점을 바꿀 수 있다면 어렵지 않은 문제

 

CODE

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int h, w;
	cin >> h >> w;
	int board[501];
	for (int i = 0; i < w; i++) {
		cin >> board[i];
	}
	int answer = 0;
	for (int i = 1; i < w-1; i++) {
		int left_max = 0;
		int right_max=0;
		for (int j = 0; j < i; j++) {
			left_max = max(left_max, board[j]);
		}
		for (int j = i + 1; j < w; j++) {
			right_max = max(right_max, board[j]);
		}
		int compare = min(left_max, right_max);
		if (board[i] < compare) {
			answer += compare - board[i];
		}
	}
	cout << answer<<endl;
	return 0;
}