[BOJ 14719] 빗물 (C++)

빗물 (Gold 5)

문제

전체 문제 보기

14719번: 빗물

접근법

이번 문제는 가장 왼쪽에서 → 가장 큰 블록 까지, 그리고 가장 오른쪽 → 가장 큰 블록까지 탐색을 통해서 빗물의 양을 구할 수 있습니다. 따라서 전체 가로의 크기 \(W\)일 때 \(O(W)\) 시간 안에 계산을 마칠 수 있습니다.

탐색방법은 복잡하지 않기 때문에 코드를 통해서 참고해 주세요.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

void InputData(int& H, int& W, vector<int>& blocks)
{
    cin >> H >> W;
    blocks.resize(W);
    for (int i = 0; i < W; ++i)
    {
        cin >> blocks[i];
    }
}
int Solve(const int H, const int W, const vector<int>& blocks)
{
    int retval{};
    const auto maxIter = max_element(blocks.begin(), blocks.end());
    const int maxIdx = distance(blocks.begin(), maxIter);

    // 왼쪽에서 오른쪽으로 탐색. (시작점에서 가장큰 블록이 있는곳 까지)
    int left = blocks.front();
    int temp{};
    for (int i = 1; i <= maxIdx; i++)
    {
        if (left > blocks[i])
        {
            temp += left - blocks[i];
        }
        else
        {
            retval += temp;
            left = blocks[i];
            temp = 0;
        }
    }
    // 오른쪽에서 왼쪽으로 탐색. (시작점에사 가장 큰 블록이 있는곳 까지)
    int right = blocks.back();
    temp = 0;
    for (int i = W - 2; i >= maxIdx; i--)
    {
        if (right > blocks[i])
        {
            temp += right - blocks[i];
        }
        else
        {
            retval += temp;
            right = blocks[i];
            temp = 0;
        }
    }

    return retval;
}
int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int H, W; // (1 ≤ H, W ≤ 500)
    vector<int> blocks;
    InputData(H, W, blocks);
    int answer = Solve(H, W, blocks);
    cout << answer;
    return 0;
}