14719 빗물

고이는 빗물의 총량을 구하는 문제

시뮬레이션, 구현 문제

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

1. 문제

---

간단 설명

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

고이는 빗물의 총량을 구하는 문제

2. 문제 분석

---

알고리즘

내 풀이

1. 입력받기
2. y = 0부터 차례로 내려가면서 블록이 있는지 확인한다
3. 블록이 있다면 현재 X좌표를 기록해두고, 오른쪽으로 자신과 동등한 높이가 있는지 확인한다
4. 자신과 동등한 높이가 있다면, 빗물이 고일 수 있으므로,    
    X좌표과 동등한 좌표의 위치 사이의 블럭만큼 고인 물의 양을 기록에 추가한다

다른 풀이. 1차원 배열 이용

1. X=0 부터 시작해서 W까지 순회한다
2. 현재블럭 기준으로 왼쪽 중 제일 큰값과, 오른쪽 기준 제일 큰 기둥을 찾는다
3. 둘 중 작은 기둥을 선택한다 (물이 고이기 위해 )
4. 선택한 작은 기둥 - 현재 기둥의 높이만큼 결과에 더해준다

주의점

• 입력받을때, 블럭을 아래부터 쌓을것인지, 위에서부터 쌓을것인지 고려해야함
  • 둘다 문제를 해결하는데 상관은 없음. 그러나 디버깅 가시성을 위해서 아래서부터 쌓았음
• 블록 좌표 X와, 동등한 높이의 좌표를 찾는 과정에서, 바로 옆에 블럭이 있다면?

필요변수

가로, 세로 H, W

2차원 배열을 저장할 map[H][W]

빗물 총량 total

그 외 계산을 위한 변수들

3. 소스코드

---

2차원 배열 이용 방법

#include <iostream>

using namespace std;

int H, W;
int map[501][501];

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> H >> W;
	for (int x = 0; x < W; x++) {
		int num; cin >> num;
		for (int y = H-1; y >= H-num; y--) {
			map[y][x] = 1;
		}
	}

	int height = 0;
	int total = 0;
	while (height < H) {
		for (int x = 0; x < W; x++) {
			// 최대 높이가 발견된 경우
			if (map[height][x] == 1) {
				// 자기와 같은 높이가 있는지 확인한다
				for (int i = x+1; i < W; i++) {
					if (map[height][i] == 1) {
						total += i - x - 1;
						break;
					}
				}

			}
		}
		height++;
	}

	cout << total;

	return 0;
}

1차원 투포인터 이용 방법

#include <iostream>

using namespace std;

int map[501];
int h, w;

// 현재 칸에 저장될 물을 구하는 함수
// 제일 왼쪽과 오른쪽에는 물이 고일 수 없으므로, 
// idx : (1,w-1)
int water(int idx) {
	int leftIdx = 0, rightIdx = w - 1;

	// 왼쪽에서 가장 큰 기둥 탐색 (0~idx)
	for (int i = 0; i < idx; i++) {
		if (map[i] > map[leftIdx]) {
			leftIdx = i;
		}
	}

	// 오른쪽에서 가장 큰 기둥 탐색 (idx~w-1)
	for (int i = idx; i < w - 1; i++) {
		if (map[i] > map[rightIdx]) {
			rightIdx = i;
		}
	}

	// 둘 중 작은 기둥 선택
	int k = min(map[leftIdx], map[rightIdx]);

	// 현재 칸에 물이 얼마나 저장될지 계산
	int res = k - map[idx];
	if (res < 0) res = 0;	// 자기보다 큰 기둥이 없어서 음수가 나오는 경우 0으로 처리

	return res;
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> h >> w;

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

	int total = 0;
	for (int i = 0; i < w - 1; i++) {
		total += water(i);
	}

	cout << total;

	return 0;
}