[백준/BOJ] 백준 8982번 : 수족관 1

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

8982번: 수족관 1

depth에 [열] = 해당 열의 깊이를 저장해 놓고, water에 [열] = 물의 양을 저장한뒤 문제를 해결했다. 그리고 구멍이 난 위치에서 왼쪽으로 확인하고 오른쪽으로 확인해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int n;
vector<int> depth(40001, 0); //[열] = 해당 열의 깊이
vector<int> water(40001, 0); //[열] = 물의 양
int k;
int y_limit;

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

	cin >> n;

	pair<int, int> before;
	pair<int, int> here;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		int x, y;

		cin >> a >> b;
		x = b;
		y = a;

		if (i == 0 || i == n - 1)
		{
			if (i == n - 1)
			{
				y_limit = y;
			}

			continue;
		}

		if (i % 2 == 1)
			before = make_pair(x, y);

		else
		{
			here = make_pair(x, y);

			for (int j = before.second; j < here.second; j++)
			{
				depth[j] = here.first;
				water[j] = depth[j];
			}
		}
	}

	cin >> k;

	for (int i = 0; i < k; i++)
	{
		int a, b, c, d;
		int x1, y1, x2, y2;

		cin >> a >> b >> c >> d;

		x1 = b;
		y1 = a;
		x2 = d;
		y2 = c;
		int out_depth; //빠질 물의 깊이

		//해당 열의 물이 다 빠진다
		for (int j = y1; j < y2; j++)
		{
			water[j] = 0;
		}

		out_depth = depth[y1];

		//왼쪽으로 가면서 확인
		for (int j = y1 - 1; j >= 0; j--)
		{
			out_depth = min(out_depth, depth[j]);

			//물이 더 빠질 수 있을때 (물이 차있는 높이가 더 높을때)
			if (depth[j] - water[j] < out_depth)
			{
				water[j] = depth[j] - out_depth;
			}
		}

		out_depth = depth[y1];

		//오른쪽으로 가면서 확인
		for (int j = y2; j < y_limit; j++)
		{
			out_depth = min(out_depth, depth[j]);

			//물이 더 빠질 수 있을때 (물이 차있는 높이가 더 높을때)
			if (depth[j] - water[j] < out_depth)
			{
				water[j] = depth[j] - out_depth;
			}
		}
	}

	int result = 0;
	for (int i = 0; i < y_limit; i++)
	{
		result += water[i];
	}

	cout << result;

	return 0;
}