[백준] 골드5 : (15989) 빗물

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

 

이 문제 구현의 핵심은, 앞에서 한 번, 뒤에서 한 번 계산하는 것이다.

 

먼저, 앞에서 끝까지 계산한다.

• 시작 위치가 0이 아닌, 3이니 시작 위치를 3으로 저장한다.
• 다음 땅의 위치를 계속 보며, 3보다 크거나 같은 땅이 나올 때까지 이동한다.
• 3보다 크거나 같지 않은 땅들은 모두 빗물이 담길 수 있는 땅이니, 저장한다.

 

• 3보다 크거나 같은 위치가 나왔다.
• 그러면, 이동안 빗물이 담길 수 있는 땅들을 순회하며, 빗물을 담아준다.
  • 처음 시작 위치(3)에서 저장된 땅의 위치(1, 2)를 뺀 값을 정답에 더한다.
• 이제, 계산을 마치고 시작 위치를 현재 위치로 갱신한다. (여기서부터 다시 계산 시작)

 

• 다음으로, 3에서 시작하면 4를 만나게 된다.
• 앞서 했던 과정을 반복한다. (어차피 빗물이 담긴 땅이 없음)
• 시작 위치가 4로 갱신되고, 또 순회를 시작한다.
• 마지막까지 다 이동했지만, 4보다 크거나 같은 땅이 없기 떄문에, 계산을 종료한다.

 

 

이 계산 방법으로 처음부터 끝까지 계산을 했다.

마지막을 보면 높이가 2이기 때문에, 빗물이 담길 수 있다.

이 떄문에 반대쪽에서 다시 계산을 시작하는 것이다.

처음 계산에서 마지막으로 높이가 가장 높았던 땅의 인덱스를 저장해 뒀다가, 이를 기점으로 반대쪽에서 다시 계산을 한다.

 

그러면, 2에서 시작해서 4에서 끝난다.

중간에 빗물이 담길 수 있는 (1, 1)을 계산해서 총합에 더한다.

 

 

최종적으로, 다음과 같이 앞쪽과 뒤쪽의 계산을 통해 총합을 구한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void Func(const vector<int>& Block, int& Answer, int Start, int& Index, bool Flag)
{
	queue<int> Save;	// 빗물이 담길 땅의 높이
	int Cur = 0;		// 현재 빗물을 담고 있는 땅의 높이

	int Ret = -1;		// 마지막으로 본 가장 높은 위치의 인덱스
						// 뒤에서 계산할 때, 이 인덱스를 기점으로 잡음

	for (int i = Start; Flag ? i < Index : i >= Index; Flag ? ++i : --i)
	{
		// 현재 빗물을 담고 있는 땅의 높이가 0이고, 현재 땅의 높이가 0이 아닌 경우 (현재 땅의 높이가 0이면 어차피 빗물을 못 담기 떄문에)
		if (Cur == 0 && Block[i] != 0)
		{
			Cur = Block[i];	// 현재 빗물을 담고 있는 땅의 높이를 현재 땅의 높이로 초기화
			Ret = i;		// 마지막으로 본 가장 높은 위치의 인덱스 저장
			continue;
		}

		// 현재 빗물을 담고 있는 땅의 높이보다 현재 땅의 높이가 같거나 큰 경우
		if (Cur <= Block[i])
		{
			// 두 땅의 위치 사이의 있는 
			while (!Save.empty())
			{
				Answer += Cur - Save.front();
				Save.pop();
			}
			Cur = Block[i];
			Ret = i; // 마지막으로 본 가장 높은 위치의 인덱스 저장
		}
		// 빗물이 담길 땅이니, 위치 저장
		else Save.push(Block[i]);
	}

	Index = Ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int Y, X, Answer = 0;
	cin >> Y >> X;

	vector<int> Block(X);
	for (int i = 0; i < X; ++i)
		cin >> Block[i];

	int Index = X;
	Func(Block, Answer, 0, Index, true);		// 시작 ~ 끝
	Func(Block, Answer, X - 1, Index, false);	// 끝 ~ 마지막으로 본 가장 높은 위치의 인덱스

	cout << Answer << "\n";
}