문제 설명
2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?
제한 사항
풀이
문제를 요약하면, 2차원의 블록의 높이에 대한 입력이 주어지면 그 블록들 사이에 고이는 물의 양을 구하는 것이다.
예를 들어,
검은색은 블록을 나타내며 하늘색은 물을 나타낸다.
위의 경우 고이는 물의 양은 5이다.
해당 문제를 해결하는 방법은 간단하다.
물은 왼쪽에서 가장 높은 블록과 오른쪽에서 가장 높은 블록 중 낮은 높이에 맞춰 고이게 된다.
1번 기둥(높이:1)의 경우, 왼쪽은 0번 기둥(높이:3)이 가장 높고 오른쪽은 4번 기둥(높이:4)이 가장 높은기둥이다.
이 중, 낮은 기둥인 0번 기둥의 높이에서 자신의 높이의 차이로 물이 고이게 된다.
즉, $min(4, 3) - 1 = 2$만큼 물이 고이게 된다.
따라서, 모든 위치에서 왼쪽과 오른쪽으로 가장 높은기둥의 높이를 알고 있으면 해결할 수 있다.
매번 계산마다 구하는 것은 비효율 적이므로 전처리를 통해 미리 값을 계산해 놓는 것이 좋다.
vector<int> Board(W);
vector<int> left(W, 0);
vector<int> right(W, 0);
for (int i = 0; i < W; i++)
{
cin >> Board[i];
}
for (int i = 1; i < W; i++)
{
left[i] = max(left[i - 1], Board[i - 1]);
}
for (int i = W-2; i >= 0; i--)
{
right[i] = max(right[i + 1], Board[i + 1]);
}
이후, 모든 기둥을 돌면서 왼쪽과 오른쪽 중 낮은 기둥에 맞춰 물이 고이는 양을 계산하면 된다.
int ans = 0;
for (int i = 0; i < W; i++)
{
int temp = min(left[i], right[i]) - Board[i] < 0 ? 0 : min(left[i], right[i]) - Board[i];
ans += temp;
}만약, 가장 높은 기둥의 경우 왼쪽과 오른쪽에 자신보다 높은기둥이 없기 때문에 결괏값이 음수가 나올 수 있다.
따라서, 음수의 경우 0으로 바꿔주어야 한다.
전체 코드
#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>
using namespace std;
int H, W;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> H >> W;
vector<int> Board(W);
vector<int> left(W, 0);
vector<int> right(W, 0);
for (int i = 0; i < W; i++)
{
cin >> Board[i];
}
for (int i = 1; i < W; i++)
{
left[i] = max(left[i - 1], Board[i - 1]);
}
for (int i = W-2; i >= 0; i--)
{
right[i] = max(right[i + 1], Board[i + 1]);
}
int ans = 0;
for (int i = 0; i < W; i++)
{
int temp = min(left[i], right[i]) - Board[i] < 0 ? 0 : min(left[i], right[i]) - Board[i];
ans += temp;
}
cout << ans;
return 0;
}