[백준 C++] 14719 빗물

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

https://www.acmicpc.net/problem/14719

문제는 되게 심플하고 재밌어보여서 선정해봤다. 정답비율이 54퍼센트라 도전해볼만도 했다.

1차원배열 blocks에 모든 데이터를 저장받고,
모든 블럭칸을 하나씩내리는 (blocks[i]--) next()함수를 먼저 정의한다.
그리고 2중포문으로 외곽반복은 높이갯수만큼, 내부는 가로갯수만큼 반복하여

이것의 예제로든다면

이런식으로 맨아래칸부터 위로 한층한층 조사한다.

여기서 pre, now의 두 변수를 포인터처럼 인덱스를 기록하게하였는데,
해당위치의 blocks[i]값이 1 이상이면 블럭이쌓인것으로판단,
좌측의 기둥(이전에체크한)을 pre 우측의 기둥(현재)을 now로보면
두 기둥사이에 빗물이 저장되게 된다.
여기서 now - pre == 1 이면 두 기둥이 붙어있는경우이므로

이전기둥을 현재위치로 갱신하고 continue

여기서 pre의 제일 처음 지정할때가 중요한데,
pre의 초깃값을 -1로 설정하여,

pre == -1 일때 pre포인터(이전기둥)을 처음 지정하는것으로 간주하여
pre 를 현재위치로 갱신하고 continue해주었다.

여기까지 전체코드의 작동 방식이다.
코드를 작성하며 두번의 실수를 한것이 있는데,

• 앞서말한 pre == -1 일때 pre = i 이후 conitnue하는 부분을 작성하지않았다.
• 매번 blocks을 탐색하기전에 pre와 now 기둥의 초기화를 지정하지 않았다..

위 두 과정을 수정하고난 전체 코드는 아래와같다.

#define _CRT_SECURE_NO_WARNINGS //scanf오류 없앰
#include <bits/stdc++.h>
using namespace std;
int H, W, res, *blocks;

void next() { //모든 블럭을 한칸씩내리는 작업
	for (int i = 0; i < W; i++) {
		blocks[i]--;
	}
}

int main(void) {
	scanf("%d%d", &H, &W);
	blocks = new int[W];
	int rain = 0;
	for (int i = 0 ; i < W; i++) { //모든블럭을 기록
		scanf("%d", &blocks[i]);
	}

	//pre, now : 기둥을 체크할 두 포인터(인덱스기록
	for (int j = 0, pre, now; j < H; j++) { 
		pre = -1; //초기화
		now = 0;
		for (int i = 0, temp; i < W; i++) {
			if (blocks[i] > 0) { //기둥이 있다면
				if (pre == -1) { //처음 기둥을 설정한다면
					pre = i; //이전기둥을 기록하고 이어서
					continue;
				}
				//인덱스1부터
				now = i; //현재기둥갱신
				if (now - pre == 1) { //두기둥이 붙어있다면
					pre = now; //이전기둥위치만 바꾸고 이어서
					continue;
				}
				//이전기둥이 설정된적이 있고 기둥사이거리가 2이상일때
				if(pre != -1 && now - pre > 1){ 
					temp = now - pre - 1; //두기둥사이에 물이고인만큼 저장
					res += temp;
					//printf("%d , %d ,   %d\n", j, i, temp);
					pre = now; //이전기둥을 갱신
				}
			}
		}
		next(); //블럭을 한칸씩내린다.
	}
	printf("%d", res);
}