[백준 14719번 / C++] 빗물

투 포인터를 활용해서 풀었다. 

 

간단하게 그림을 그려서 설명하겠다. 

 

위의 그림처럼 Start 인덱스에서 물이 채워지는 양은 

Start 인덱스 기준으로 왼쪽 블락과 오른쪽 블락을 확인해야 한다. 

즉, 현재 블럭의 높이보다 큰 값중에 왼쪽에서의 블락의 최댓값과 오른쪽에서의 블락의 최댓값을 구해서 

빼주면 되는것이다.

 

result += min(L_max, R_max) - v[Start]  

 

* 물이 넘치게 되면 작은 블락을 넘기기 때문에 양쪽 블락 중 작은 값을 구한다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{       
    int m, n; 
    cin >> m >> n; 
    vector <int> v; 
    for (int i = 0; i < n; i++) {
        int a; cin >> a; 
        v.push_back(a); 
    }
    int result = 0; 
    for (int i = 1; i < n - 1; i++) {
        int l = 0; 
        int r = 0; 
        for (int j = 0; j < i; j++) {
            if (v[i] < v[j])l = max(l, v[j]); 
        }
        for (int j = i + 1; j < n; j++) {
            if (v[i] < v[j])r = max(r, v[j]); 
        }
        if(l&&r)result+= min(l, r) - v[i]; 
    }
    cout << result; 

}

 

14719번: 빗물