백준 14719 빗물

BOJ 14719

목표 : 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;
}

위의 방법을 왼쪽에서 출발하고 다시 오른쪽에서 출발해 정답을 구할 수 있다.