Week 5 (구현) - 문제 14719번 (빗물)

문제:

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력:

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력:

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제 입력1:

4 4
3 0 1 4

예제 출력1:

5

예제 입력2:

4 8
3 1 2 3 4 1 1 2

예제 출력2:

5

예제 입력3:

3 5
0 0 0 2 0

예제 출력3:

0

코드:

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

int H, W;		//세로 길이와 가로 길이 변수
int answer = 0;

int main()
{
	//문제의 첫 번째 문장 입력받기
	cin >> H >> W;
	
	//벡터 선언
	vector<int> Ground(W);

	//벡터 (지형 정보) 받기
	for (int& i : Ground)
		cin >> i;

	//첫번째 지형부터 빗물 칸 더하기
	for (int i = 1; i < W-1; i++)
	{
		int left = 0; int right = 0;

		//현재 칸의 왼쪽 중 가장 큰 값
		for (int j = 0; j < i; j++)
		{
			left = max(left, Ground[j]);
		}

		//현재 칸의 오른쪽 중 가장 큰값
		for (int k = W - 1; k > i; k--)
		{
			right = max(right, Ground[k]);
		}

		//오른쪽과 왼쪽 값중 작은 값을 빼서 0과 비교해서 더 큰 값 넣기
		answer += max(0, min(left, right) - Ground[i]);
	}

	cout << answer;

	return 0;
}

설명:

for (auto i : Ground)
		cin >> i;

위 코드가 안되는 이유

위와 같이 쓴다면 auto는 int로 추정된다.

그러나 int i가 된다면, 배열에 대한 값이 복사가 되기 때문에 값을 바꿀 수 없다..

즉 0인 값이 계속 그대로 유지되는 것이다.

그래서 복사가 아닌 &를 사용해 참조를 하여 값을 바꿀 수 있다.

따라서 올바른 코드는 아래와 같다.

for (int& i : Ground)
    cin >> i;

참고자료 (https://computer-science-student.tistory.com/79)

 

알고리즘에 대하여

한 세로줄씩 검사하는데, 해당줄의 왼쪽편과 오른쪽 편에서 가장 큰 값을 각각 비교한다.

두 값중 작은 값을 뽑아 현재 줄의 값과 빼서 결과 값에 더한다.

이 과정을 모든 줄 (끝에 두 줄을 제외한) 에 적용하여 값을 구한다.