[BOJ] 26580번 : Rain C++ 풀이

배열로 높이가 주어질때, 물을 채운다고 생각해보자. 결국 물을 넘칠때까지 따르면 정답을 구할 수 있다.

각 칸을 기준으로 최대 높이 몇까지 채워질 수 있을까?

i에 물을 최대한 채울때, 왼쪽과 오른쪽을 전부 살펴보자. 이때 왼쪽에서 제일 높은 높이와 오른쪽에서 가장 높은 높이가 물을 채울 수 있는 기준이 된다는 것을 알 수 있다. 그리고 이 두 값중 작은 값까지 물을 채울 수 있으므로, 이 높이에 대해 O(2N)으로 전처리를 수행하면 간단하게 구할 수 있다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 2000000000
#define MOD 10007
#define NUM 100010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int N, l[NUM], r[NUM];


vector<string> split(string input, char delimiter) {
    vector<string> answer;
    stringstream ss(input);
    string temp;
    while (getline(ss, temp, delimiter)) {
        answer.push_back(temp);
    }
    return answer;
}


void init() { 
    cin >> N;
    cin.ignore();
    for (int i=0; i<N; i++) {
        int answer = 0;
        for (int j=0; j<NUM; j++) l[j] = 0, r[j] = 0;
        string s;
        getline(cin, s);
        vector<string> v = split(s, ' ');
        for (int j=0; j<v.size(); j++) {
            int num = stoi(v[j]);
            l[j] = num;
            r[j] = num;
        }
        for (int j=1; j<v.size(); j++) {
            l[j] = max(l[j], l[j-1]);
        }
        for (int j=v.size()-2; j>=0; j--) {
            r[j] = max(r[j], r[j+1]);
        }
        for (int j=1; j<v.size()-1; j++) {
            int num = min(l[j], r[j]);
            if (stoi(v[j]) >= num) continue;
            answer += (num - stoi(v[j])); 
        }
        cout << answer << '\n';
    }
}       

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