백준 14719번 빗물 (C++) 🚩

오답 - 1%에서 틀렸습니다 

 

접근1. 

1) 지금 위치 다음이 더 높이가 높으면 채울수 있다 가정  (arr[i]) 

2) 지금 위치 기준 왼쪽에서 제일 높은 위치의 높이와 비교해서 더 작은 높이로 arr[max_idx]=max_h

3) (지금 위치에서 제일 높은 위치) x ( min(arr[i],arr[max_idx])-arr[i]) 를 곱해주고, 

4) arr[i+1]와 비교하여 max_ h와 max_idx를 갱신해준다.

 

문제점: 

- 지금 위치 기준 왼쪽으로 칸을 더할때 칸의 높이가 다 다르므로 3)에서 min(arr[i],arr[max_idx])-arr[i] 이부분 고쳐야함 

- 지금 위치보다 바로 다음이 더 큰걸 만날때 한번에 왼쪽을 채우고 넘어가려고 max_idx,max_h를 arr[i+1]과 비교해서 갱신해줬는데 만약 맨 처음과 맨 끝이 가장 높이가 길면 위쪽에 채우지 못한 공간 있는채 탐색 끝남 

- arr[i+1]이 제일 높을경우 그 다음부터 탐색해야되는데 이부분 구현 x , 그리고 한번에 채우니까 제일 높은게 제일 왼쪽에 있으면 중복으로 채우게됨

 

-> 오른쪽 기준을 바로 다음 높이로(윗부분 빈공간생김) , 한번에 채움(제일 높은 위치가 계속 맨 왼쪽이면 중복으로 채우게 됨)이 문제점 

#include <iostream>
#include <vector>

using namespace std;

int main() {

	int sum = 0;

	int h, w;
	cin >> h >> w;

	vector<int>arr;
	int t;

	for (int i = 0; i < w; i++) {
		cin >> t;
		arr.push_back(t);
	}

	int max_h = arr[0];
	int max_idx = 0;
	
	for (int i = 1; i < w - 1; i++) {

		if (arr[i] < arr[i + 1]) { 


			if (max_h <= arr[i + 1]) { 
				sum += (i - max_idx) * (max_h - arr[i]);
				max_h = arr[i + 1];
				max_idx = i + 1;
			}
			else {
				sum += (i - max_idx) * (arr[i + 1] - arr[i]);
			}
			
		}
	
	}
	cout << sum;

}

 

 

정답

 

-  오른쪽 기준을 지금 위치에서 바로 다음으로 고정하니까 빈공간이 생김 -> 오른쪽에 어디든 더 큰게 있으면 언젠가 채워져야하므로 오른쪽 기준도 오른쪽에 있는 가장 큰 높이로 지정 

- 접근 1의 가정 1)로 왼쪽으로 한번에 채우는게 아니라 각 칸마다 채울수 있는 높이까지 모두 채워주기 

#include <iostream>
#include <vector>

using namespace std;

int main() {

	int sum = 0;

	int h, w;
	cin >> h >> w;

	vector<int>arr;
	int t;

	for (int i = 0; i < w; i++) {
		cin >> t;
		arr.push_back(t);
	}
	

	for (int i = 1; i < w - 1; i++) {
		int left = 0;
		int right = 0;
		//왼쪽 기둥찾기 
		for (int j = 0; j < i; j++) {
			left = max(left, arr[j]);
		}


		//오른쪽 기둥 찾기 
		for (int j = i+1; j < w; j++) {
			right = max(right, arr[j]);
		}
		//for (int i = left + 1; i < right; i++) {
		sum += max(0, min(left, right) - arr[i]);
		//}

	}
	cout << sum;

}

 

사실 구글링으로 힌트를 보았지만.. 골드 5인데 어렵게 느껴졌다.