[백준][C++] 14719: 빗물

문제

14719번: 빗물

풀이

구현, 시뮬레이션

 

풀이 1

• 현재 칸에서 왼쪽에 위치한 블록들 중 최고 높이와 오른쪽에 위치한 블록들 중 최고 높이를 구한다. 
• 현재 칸에서는 최고 높이들 중에서 작은 값과 현재 높이의 차만큼의 물이 찬다. 

 

풀이 2

• 한 행에서 물이 차는 칸을 계산한다. 
• 현재 행에서 블록과 블록으로 막히는 칸들은 물이 차는 칸이다. 
• 행에서 0번 열부터 시작하여 W - 1번 열까지 탐색한다. 
• 처음 블록이 등장했다면 flag를 true로 설정한다. 
• flag가 true로 설정된 상태에서 빈 칸이 등장한다면 current_water에 1을 추가하여 블록 사이의 빈 칸의 개수를 센다. 
• 다음 블록이 등장했다면 현재까지 빈 칸의 개수를 정답에 더한다. 

코드

풀이 1 

#include <iostream>
#include <algorithm>

using namespace std;

int ground[500];

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

	int H, W;
	cin >> H >> W;

	for (int i = 0; i < W; ++i)
	{
		cin >> ground[i];
	}

	int answer = 0;
	for (int i = 0; i < W; ++i)
	{
		int left_maxi = 0;
		int right_maxi = 0;

		// 현재 칸에서 왼쪽에 위치한 블록들 중 최고 높이
		for (int j = i - 1; j >= 0; --j)
		{
			left_maxi = max(left_maxi, ground[j]);
		}

		// 현재 칸에서 오른쪽에 위치한 블록들 중 최고 높이
		for (int j = i + 1; j < W; ++j)
		{
			right_maxi = max(right_maxi, ground[j]);
		}

		answer += max(0, min(left_maxi, right_maxi) - ground[i]);
	}

	cout << answer;

	return 0;
}

풀이 2

#include <iostream>
#include <algorithm>

using namespace std;

int ground[500];

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

	int H, W;
	cin >> H >> W;

	for (int i = 0; i < W; ++i)
	{
		cin >> ground[i];
	}


	int answer = 0;
	for (int i = 0; i < H; ++i)
	{
		int current_water = 0;
		bool wall_flag = false;

		for (int j = 0; j < W; ++j)
		{
			if (ground[j] > i)
			{
				if (wall_flag == true)
				{
					answer += current_water;
					current_water = 0;
				}
				else
				{
					wall_flag = true;
				}
			}
			else
			{
				if (wall_flag == true)
				{
					current_water++;
				}
			}
		}
	}

	cout << answer;

	return 0;
}