[G5] 백준 14719번 빗물 C++ 구현

리뷰

 

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

블록으로 이루어진 2차원 세계에서 고이는 빗물의 총량을 구하는 문제

가로 길이가 500밖에 되지 않아서 진짜 뇌빼고 아무생각 없이 구현하면 풀린다.

 

전역 변수

1. h, w : 2차원 세계의 블록의 최대 세로 길이 h와 가로 길이 w
2. ans : 정답을 저장하고 출력할 변수
3. nodes : 블록의 높이 정보를 저장할 정수형 배열, 크기는 502보다 크게만 해주면 된다.

 

함수

없음

 

 

문제풀이

1. h와 w를 입력 받고, w개의 블럭을 nodes에 입력받아 준다, 이때 각 블럭의 인덱스는 1 ~ w로 지정해 준다.
2. 양쪽 끝의 벽을 뺀 2 ~ w - 1에 있는 블럭들을 순회해 준다.
3. 자신 기준 왼쪽에서 가장 큰 값 l, 오른쪽에서 가장 큰 값 r을 구해준다.
4. 둘 중 작은 값에서 자신의 블록 높이를 뺀 값을 ans에 더해준다.
5. 탐색이 종료되었다면 ans에 저장된 값을 출력해 준다.

 

참고 사항

1. 큰 값을 찾을때 0도 포함해야 하므로 1-based-index로 구현하였다.
2. 즉, 왼쪽 오른쪽에 0이 존재해야 하므로 nodes배열을 전역변수로, 크기를 502 이상으로 해준 것이다.
3. 양쪽의 최대값 중 작은값에서 자신을 뺄 때 음수가 나올 수 있으므로 max 0처리를 해주어야 한다.

 

정답 코드

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

int h, w, ans;
int nodes[555];

int main() {
	cin >> h >> w;
	for (int i = 1; i <= w; i++) cin >> nodes[i];
	for (int i = 2; i < w; i++) {
		int *l = max_element(nodes, nodes + i);
		int *r = max_element(nodes + i + 1, nodes + w + 1);
		
		ans += max(0, min(*l, *r) - nodes[i]);
	}
	cout << ans;
}