[백준 / C언어] 14719번: 빗물

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

14719번: 빗물

 

난이도: solved.ac 골드 5

 

알고리즘 분류

---

구현, 시뮬레이션, 투포인터

 

접근 방법

---

물이 차려면 양쪽의 높이보다 더 낮은 높이를 가져야 한다.

이때 차는 물은 양쪽의 높이에서 더 낮은 쪽의 높이를 가진다.

그리고 항상 특정 지점을 둘러싼 곳에서, 두 번째로 높은 지점의 높이로 물이 찬다.

아래 그림에서 1번부터 5번 사이의 구간을 보자.

1번부터 5번 사이에서 두 번째로 높은 지점은 1번 지점인데, 1번부터 5번 사이에서 1번 지점보다 더 낮은 지점은 1번의 높이까지 물이 찬다.

5번부터 8번 사이의 구간도 마찬가지다.

5번부터 8번 사이 중 두 번째로 높은 지점은 8번 지점인데, 그 사이에서 8번보다 낮은 지점은 8번의 높이까지 물이 찬다.

 

구현

---

위의 성질을 이용해 양 끝에 포인터 left와 right를 두고, left와 right 중 더 낮은 쪽의 높이까지 물을 채웠다.

그리고 더 낮은 쪽에서 포인터를 가운데 쪽으로 한 칸 이동시켜 left >= right가 될 때까지 위의 과정을 반복하였다.

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define Min(a,b) ((a)<(b)?(a):(b))
 
int main() {
	int H, W, cnt = 0;
	scanf("%d %d", &H, &W);
	int* arr = (int*)calloc(W, sizeof(int));
	for (int i = 0; i < W; i++)
		scanf("%d", &arr[i]);
 
	int left = 0, right = W - 1, min, start, end;
	while (left < right) {
		min = Min(arr[left], arr[right]);
		start = left + 1;
		end = right;
		while (start < end) {
			if (arr[start] < min) {
				cnt += min - arr[start];
				arr[start] = min;
			}
			start++;
		}
		if (min == arr[left])
			left++;
		else
			right--;
	}
	printf("%d", cnt);
	free(arr);
	return 0;
}