목표 : 2차원 세계에 블록이 있다. 비가 오면 블록 사이에 고인 빗물을 구하자.
조건 : 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)
이 문제는 두 가지 방법으로 해결할 수 있다. 반복문을 활용한 방법과 포인터를 활용한 방법이 있다.
우선 반복문을 활용한 방법은 빗물은 블록이 없는 빈 공간에만 존재할 수 있다. 각 높이의 양쪽 끝에서 블록을 만날 때까지 빈 공간을 체크하고 해당 공간을 제외한 영역의 넓이를 출력한다.
#include <stdio.h>
using namespace std;
int block[501][501];
int N, M, ans;
int main() {
scanf("%d%d",&N,&M);
for (int i = 0; i < M; i++){
int a;
scanf("%d",&a);
for (int j = 0; j < a; j++){ // block 설치
block[j][i] = -1;
}
}
for (int i = 0; i < N; i++){
int next = 0;
while(!block[i][next]){
block[i][next] = 1;
next++;
}
next = M-1;
while(!block[i][next]){
block[i][next] = 1;
next--;
}
for (int j = 0; j < M; j++){
if (!block[i][j]){
ans++;
}
}
}
printf("%d\n",ans);
return 0;
}
다음은 포인터를 활용한 방법이다. 빗물이 고일려면 맨앞이나 맨뒤의 블럭보다 낮은 블럭들이 중간에 쌓여야 한다. 3단계로 고일 빗물을 구할 수 있다.
1. 빗물이 고이는 구간의 맨앞의 블록의 높이를 설정한다.
2. 맨앞의 블록보다 크거나 같은 블록을 만날 때 까지 고이는 빗물의 넓이를 더한다.
3. 맨앞의 블록보다 큰 블록을 만났다면 정답에 고이는 빗물의 넓이를 더하고 해당 블록이 맨앞의 블록이 된다.
#include <stdio.h>
#include <vector>
using namespace std;
int N, M, ans;
vector<int> V;
int main() {
scanf("%d%d",&N,&M);
for (int i = 0; i < M; i++){
int a;
scanf("%d",&a);
V.push_back(a);
}
int tmp = 0, lpt = 0, rpt = M-1;
for (int i = 0; i < M; i++){
if (V[lpt] > V[i]){
tmp += V[lpt]-V[i];
}
else{
ans += tmp;
tmp = 0;
lpt = i;
}
}
tmp = 0;
for (int i = M-1; i >= lpt; i--){
// 오른쪽에서 부터 빗물이 고이지 못한 왼쪽의 맨앞블록까지
if (V[rpt] > V[i]){
tmp += V[rpt]-V[i];
}
else{
ans += tmp;
tmp = 0;
rpt = i;
}
}
printf("%d\n",ans);
return 0;
}
위의 방법을 왼쪽에서 출발하고 다시 오른쪽에서 출발해 정답을 구할 수 있다.