14719번: 빗물

Memo

• 벽을 기준으로 코드를 작성하면 매우 어려워 지는 문제였습니다.
• 빗물을 바닥으로부터 한 칸씩 증가시켜 가며 직사각형의 넓이를 구하는 방식을 얼마나 빠르게 생각해 내느냐가 관건입니다.

Code

제출 날짜

2021/03/29

메모리

2020 KB

시간

0 ms

#include <iostream>

int blocks[502];
int H, W;
int ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> H >> W;
	for (int i = 0 ; i < W ; i++)
		std::cin >> blocks[i];
}

void solve()
{
	int l_block;

	for (int i = 1 ; i <= H ; i++)
	{
		l_block = -1;
		for (int j = 0 ; j < W ; j++)
		{
			if (blocks[j] >= i)
			{
				if (l_block == -1)
				{
					l_block = j;
					continue;
				}
				ans += (j - l_block - 1);
				l_block = j;
			}
		}
	}
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}