c언어 14719번 빗물 (백준)

#include <stdio.h>

int main(void)
{
	int a[501] = {0};
	int sum = 0;
	int h, w; //높이, 가로
	scanf("%d%d", &h, &w);
	//index 변수 초기화
	int i = 0; 
	int j = 0;
	for(i = 0; i<w; i++) scanf("%d", &a[i]);
	
	for(i=0; i<h; i++)
	{
		int sw = 0; //스위치 : 빗물을 담을 칸을 세기 시작함
		int count = 0; //빈칸의 개수를 담는 변수
		for(j=0; j<w; j++) {
			
			if(sw==1 && a[j] == 0) count++; //스위치가 켜진 상태에서, a[j]가 0 즉 빈칸 일 경우
			
			if(a[j] > 0 && sw == 0) sw = 1; //맨 처음으로 검정색이 들어오면 스위치 on
			
			if(a[j] > 0 && sw == 1 && count > 0) //검정색이며, 스위치는 켜져있고, 검정칸들 사이에 빈칸이 있을 때
			{
				sum += count; //구한 빈칸을 sum에 누적
				count = 0; //다시 빈칸을 담았던 변수엔 0을 대입
			}
			
			if(a[j] > 0) { //높이가 1씩 증가할 때마다, 입력받은 숫자들의 크기는 1씩 줄어듬
				a[j]--; //ex) 1층 : 3 0 1 4 -> 2층 : 2 0 0 3 -> 3층 : 1 0 0 2 -> 4층 : 0 0 0 1
			}
		}
	}
	printf("%d", sum); //빗물을 담을 수 있는 칸의 개수를 출력
	
	return 0;
}

 

 

0) 빗물을 받을 수 있는 칸 : 양 옆이 칸으로 막힌 빈칸들

고로, 한쪽이라도 블록으로 막혀있지 않는다면, 빗물을 담을 수 없다.

 

빗물을 받을 수 있는 칸 구하기

 

1) 각 층마다, 빗물을 받을 수 있는 칸을 구한다.

 

2) 각 층에서, 검은 칸이 있는 부분부터 빈칸을 구하기 시작한다.

 

3) 빈칸을 구하기 시작한 이후, 빈칸이 1 이상 있는 후에, 다시 검은 칸이 나오면, 그 전까지 구한 빈칸의 개수를 전체 빗물 칸에 누적시킨 후, 다시 빈칸의 개수를 0부터 구하러 간다.

 

4) 층이 증가될 때마다, 입력받았던 블록의 개수를 1씩 줄인다.

(이유 : 높이가 1씩 증가한다는 것은, 모든 블럭의 개수를 1씩 (0개인 경우는 제외) 줄인 것과 같기 때문이다)

 

5) 전체 빗물 칸의 개수를 출력한다.

 

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

14719번: 빗물