은근히 까다로운 구현 문제였다.
2차원 세계 바깥쪽은 블록이 없기 때문에 빗물이 고이지 않는다. 따라서 첫번째와 마지막 블록의 높이가 중요하다고 볼 수 있다.
필자는 주어진 배열에서 블록의 높이가 가장 높은 인덱스를 찾은 다음, 양 끝을 시작점으로 하여 두개의 포인터가 높이가 가장 높은 인덱스를 향해 가도록 구현하였다.
#include <iostream>
#include <queue>
using namespace std;
int H, W;
int block[501];
int getHighestIndex() {
int highest = block[0];
int idx = 0;
for(int i=1; i<W; i++)
if (highest <= block[i]) {
highest = block[i];
idx = i;
}
return idx;
}
int getRainWater() {
queue<int> qFront, qBack;
int highIdx = getHighestIndex();
int frontHigh = 0, backHigh = 0;
int ret = 0;
for (int i = 0; i < W; i++) {
int front = i;
int back = W - 1 - i;
if (front <= highIdx) {
if (frontHigh > block[front]) {
qFront.push(block[front]);
}
else {
while (!qFront.empty()) {
ret += frontHigh - qFront.front();
qFront.pop();
}
frontHigh = block[front];
}
}
if (back >= highIdx) {
if (backHigh > block[back]) {
qBack.push(block[back]);
}
else {
while (!qBack.empty()) {
ret += backHigh - qBack.front();
qBack.pop();
}
backHigh = block[back];
}
}
}
return ret;
}
int main(void) {
cin >> H >> W;
for (int i = 0; i < W; i++)
cin >> block[i];
cout << getRainWater() << endl;
return 0;
}
'알고리즘 > BOJ' 카테고리의 다른 글
백준 2839번: 설탕 배달 (0) | 2022.10.14 |
---|---|
백준 1662번: 압축 (0) | 2021.10.23 |
백준 1107번: 리모컨 (0) | 2021.10.22 |
백준 12015번: 가장 긴 증가하는 부분수열 2 (0) | 2021.10.22 |
백준 1939번: 중량제한 (0) | 2021.10.22 |