문제
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);
}
