백준 BOJ 14719 - 빗물

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

14719번: 빗물

브루트포스 문제이다.

어떠한 위치 i에서 고일수 있는 물의 양은,

그 양쪽으로 i보다 높이가 높은 두개의 블록 l,r 이 있을때,

min(l,r) - i 만큼 고일 수 있다.

 

모든 i에 대해서 순회하는데 O(N),

높이가 최대로 높은 두 블록 l,r 을 찾는데 O(N)으로

전체 시간복잡도는 O(N^2) 이다.

 

위치 i에서 l,r을 찾고자 할때,

l이나 r이 존재하지 않는 경우가 있을수 있는데,

이 경우에 음수가 더해지는것을 막기 위해서

l과 r은 처음에 i의 높이로 초기화해주어야 한다.

 

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

int N,M;
int arr[1234] = {0};

int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++) cin >> arr[i];
	
	int ans = 0;
	for(int i=0; i<M; i++){
		int l = arr[i];
		int r = arr[i];
		
		for(int j=0; j<M; j++){
			if(j<i){
				l = max(l, arr[j]);
			}
			if(i<j){
				r = max(r,arr[j]);
			}
		}
		
		//printf("[%d]", min(l,r)-arr[i]);
		
		ans += min(l,r)-arr[i];
	}
	cout << ans;
}