백준 14719 - 빗물(C++)

 

처음 이 문제를 풀 때는 물 웅덩이가 생기는 부분이 작은 단위로 쪼개서 생각해야한다고 잘못 접근하였다.

그러다 그릇처럼 생각해보았을 때 양끝의 높이의 최저와 내 위치에서의 높이의 차가 웅덩이 깊이가 된다는 것을 알았다.

즉, 내 위치 기준으로 왼쪽으로 최고 높이, 오른쪽으로 최고 높이를 찾고, 더 낮은 최고 높이와 나의 높이를 빼는 것이다.

 

위 그림을 보면 분홍색이 현재 위치일 때, 왼쪽 노랑 블록이 왼쪽 최고 높이, 오른쪽 노랑 블록이 오른쪽 최고 높이가 된다. 왼쪽 노랑 블록이 더 작으므로 분홍 블록에서의 웅덩이 높이는 [왼쪽 블록 높이 - 분홍 블록 높이]이 된다. 

	int high, width;
	cin >> high >> width;
	int arr[501] = { -1, }; 
	int left = 0, right = arr[width-1]; //최고점을 찾기 위한 인덱스 변수
	int left_max = 0, right_max = 0; //최고점을 저장할 변수
	int water=0, mywater=0; //전체 물양과 현재 위치에서의 물의 양
	
    for (int i = 0; i < width; i++) 
		cin >> arr[i];
        
	for (int i = 1; i < width-1; i++) {
		left_max = 0, right_max = 0;
		left = i - 1; //내 기준 왼쪽으로 찾음
		right = i + 1;// 내 기준 오른쪽으로 찾음
        
		while (left >= 0) {
			if (arr[left] >= left_max) left_max = arr[left];
			left--;
		}
        
		while (right <= width - 1) {
			if (arr[right] >= right_max) right_max = arr[right];
			right++;
		}
       
         //두 최고점 중 최저를 이용하여 물의 높이를 구함
		if (left_max > right_max ) mywater = right_max - arr[i];
		else mywater = left_max - arr[i];

		if (mywater < 0) mywater = 0;
		water += mywater;
	}

	cout << water << endl;