문제
2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?
입력
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로길이 W가 주어진다. (1 ≤ H, W ≤ 500)
두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.
따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.
출력
2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.
빗물이 전혀 고이지 않을 경우 0을 출력하여라.
🔎문제 해석
빗물이 고이는 조건, 상황을 잘 생각해보면 쉽게 풀 수 있는 문제다.
특정 칸을 기준으로 왼쪽방향에서 가장 높은 기둥과, 오른쪽 방향에 가장 높은기둥의 높이를 구해준다.
빗물은 왼쪽,오른쪽 방향의 가장 높은기둥 중 더 작은 방향의 기둥 높이만큼 빗물이 고인다.
예시를 들어서 설명해보겠습니다.
빗물이 고이기 전 사진입니다.
과정은 아래와 같습니다.
- 각 지점에서 왼쪽방향, 오른쪽 방향으로 가장 높은기둥의 높이를 찾습니다.
- 첫 번째 화살표 지점에서는 왼쪽방향은 3 / 오른쪽방향은 4가 될 것입니다.
- 그렇다면 빗물은 왼쪽과 오른쪽 중 더 작은 높이인 왼쪽방향의 기둥 높이만큼 고이게 될 것입니다.
- 고이는 빗물의 양은 3번에서 구한 높이에서 본인의 기둥높이를 뺀 만큼 빗물이 고이게 됩니다.
- 만약 3번 과정에서 구한 높이에서 본인의 기둥높이를 뺏는데, 음수가 나온다면 그 위치는 빗물이 고이지 못합니다.
- 예를 들어서 기둥의 높이가 4인 것을 기준으로 탐색을 시작합니다.
- 왼쪽 기둥 : 3 / 오른쪽 기둥: 3이 될 것입니다.
- 둘 다 높이가 같기 때문에 3-4 = -1만큼 고이게 될 것입니다.
- 하지만 여기서 -1만큼 고인다는 말은 없기에, 해당 기둥에서는 빗물이 고이지 못하는 것입니다.
- 예를 들어서 기둥의 높이가 4인 것을 기준으로 탐색을 시작합니다.
- 이렇게 각 지점마다 왼쪽, 오른쪽으로 탐색을 해서 본인의 기둥에서 작은 높이의 기둥높이만큼 뺀 값을 계속 더해주면 됩니다.
모든 과정을 끝낸 후 아래와 같은 모양이 될 것입니다.
💻코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int h, w; // h세로, w 가로
vector<int> rain;
int main()
{
cin >> h >> w;
rain.resize(w, 0);
for (int i = 0; i < w; i++)
{
cin >> rain[i];
}
int total =0;
for(int i=0;i<w; i++){
int left = 0,right = 0;
for(int j=0; j<i; j++){ //기준점의 왼쪽방햐엥서 가장 높은 기둥의 높이 구하기
left =max(left,rain[j]);
}
for(int j=w-1; j>i; j--){ //기준점의 오른쪽방향에서 가장 높은 기둥의 높이 구하기
right = max(right,rain[j]);
}
//다 돌면 기준점마다 왼쪽방향에서 가장 큰값, 오른쪽 방향에서 가장 큰 값을 뽑아냄.
if(min(left,right)-rain[i]>=0){ //값이 0보다 크다면 담을수 있다는 뜻임..
total+=min(left,right)-rain[i]; //왼쪽,오른쪽중 더 낮은 높이의 기둥만큼 물이 고임.
}
}
cout<<total<<endl;
}
😀느낀 점
- 빗물이 고인다는 그 상황 자체를 이해하면 쉽게 풀 수 있는 문제다.
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준 1022] - 소용돌이 예쁘게 출력하기(C++)[골드4] (0) | 2023.03.11 |
---|---|
[백준 20164] - 홀수 홀릭 호석(C++)[골드5] (0) | 2023.03.08 |
[백준 21758] - 꿀 따기(C++)[골드5] (0) | 2023.03.06 |
[백준 12851]- 숨박꼭질2 (C++)[골드4] (0) | 2023.03.04 |
[백준 1976] - 여행가자(C++)[골드4] (0) | 2023.03.04 |