BOJ-8982-수족관 1

필요한 지식

1. 시뮬레이션

접근

• 구멍을 기준으로 좌/우 를 봐준다.

• 구멍이 선분으로 주어지는데 (x1,y1,x2,y2) 여기서 필요한 건 x1하나이다. 처음 코드를 작성할 때에는 4가지를 모두 사용하도록 구현했었는데 x1하나만 사용하므로써 코드가 많이 간결해지고 구현이 난이도가 많이 줄어든다.

• 좌/우를 봐줄때, height 에는 구멍의 높이를 저장해 주고, 한 칸씩 이동할 때마다 height는 wall[j]와 비교하여 둘 중 최대값으로 갱신시키고, water[j]는 height와 비교하여 둘중 작은 값을 넣는다.

• height : 바닥의 높이와 빠진 물의 높이중 더 값이 낮은 높이

• wall[i] : i번째 바닥 높이

• water[i] : i번째 칸의 최대로 빠졌을 때의 물의 높이

• j번째 구멍에서 좌/우 로 진행중에 다른 구멍을 만나게되면 멈춰서 시간을 줄였다.

코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>wall, water, hole;
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	int a, b; cin >> a >> b;
	for (int i = 0; i < n / 2-1; i++) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		for (int s = a; s < c; s++) wall.push_back(b);
	}
	cin >> a >> b;
	water.resize(wall.size());
	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		hole.push_back(a);
	}
	for (int i = 0; i < hole.size(); i++) {
		//좌
		int height = wall[hole[i]];
		for (int j = hole[i]; j >= 0; j--) {
			if (i > 0 && (hole[i - 1] == j)) break;
			height = min(height, wall[j]);
			water[j] = max(water[j], height);
		}
		//우
		height = wall[hole[i]];
		for (int j = hole[i]; j < wall.size(); j++) {
			if (i < hole.size() - 1 && (hole[i + 1] == j)) break;
			height = min(height, wall[j]);
			water[j] = max(water[j], height);
		}
	}

	int ans = 0;
	for (int i = 0; i < water.size(); i++) {
		if (water[i] - wall[i] < 0) ans += wall[i]-water[i];
	}
	cout << ans;
	return 0;
}

결과