문제 설명
수족관에 구멍이 났다! 수족관과 구멍이 주어졌을 때 수족관에 남아있는 물의 양을 구하는 문제입니다.
풀이
처음에는 수족관을 좌표로 입력받아서 좀 무서웠는데 문제를 읽어보고 생각을 좀 해보니 구현 문제였습니다.
입력으로 주어지는 좌표를 저장하기 위해서
arr[i] = { i 번째 가로 선분 왼쪽 x좌표, i 번째 가로 선분 오른쪽 x좌표}
d[i] = {i 번째 가로 선분 y좌표, 가로 선분 범위 물의 y좌표}
pair나 구조체를 사용하겠습니다.
가로 선분 단위로 저장하는 이유는 구멍이 수평 선분으로 주어져 있어서 그렇습니다.
다음으로는 구멍의 개수와 좌표가 주어지는데
h[i] = i 번째 가로 선분이 구멍인가?
를 저장해 주시면 됩니다.
arr 배열에서 구멍의 좌표와 동일한 좌표를 찾은 뒤 h를 체크해 주시면 됩니다.
이제 가로선 분들과 수족관 높이와 물의 높이, 구멍의 위치를 알고 있으니 이 정보로 수족관에 남아있는 물의 양을 구해보겠습니다.
파란색 선이 구멍입니다.
구멍을 입력받을 때마다 좌로 한번 우로 한번 쭉 보면서 물의 높이를 조절하는 방법도 있지만
저는 시간을 조금이라도 줄여보려고 한 번에 구멍을 입력받고 가로 선분을
가장 왼쪽에서 오른쪽으로 한번, 가장 오른쪽에서 왼쪽으로 한번 보면서 높이를 구하겠습니다.
왼쪽에서 오른쪽을 보면서 구멍 기준으로 오른쪽에 있는 물의 높이를 구하고
오른쪽에서 왼쪽을 보면서 구멍 기준으로 왼쪽에 있는 물의 높이를 구하려고 합니다.
water - 현재 물의 y좌표
일단 현재 위치에 구멍이 존재하면 구멍에서 물이 다 빠지기 때문에 물의 y좌표는 구멍의 위치 y좌표가 됩니다.
구멍이 존재하지 않을 때는 물의 y좌표가 현재 위치의 수족관 y좌표보다 클 때는 현재 위치에 물이 있을 수 없습니다.
그렇기 때문에 물의 y좌표에 현재 위치의 y좌표를 저장하겠습니다.
물의 y좌표가 현재 위치의 수족관 y좌표보다 작을 때는 물이 그만큼 차 있을 수 있기 때문에 그대로 물의 y좌표를 저장해 줍니다.
물의 y좌표 = max(min(물의 y좌표, 현재 위치의 수족관 y좌표), 현재 위치의 물의 y좌표)
물의 y좌표는 수족관 y좌표와 물의 y좌표를 비교해 더 작은 값을 저장합니다.
그렇게 되면 위에서 말한 두 조건에 만족하는 물의 y좌표를 구할 수 있습니다.
현재 위치의 물의 y좌표와 water 중에 최댓값을 저장해 줘야 합니다.
현재 위치의 물의 y좌표를 구하는 과정인데 왜죠…?
처음에 가장 왼쪽에서 오른쪽으로 한번 돌 때는 상관이 없지만
두 번째 오른쪽에서 왼쪽으로 돌면서 구할 때 현재 위치 y좌표가 이미 저장되어 있기 때문에
그중에 y좌표의 최댓값을 구하여 물이 빠질 수 있는 만큼 빼줍니다.
물의 y좌표가 구해졌으면 현재 위치의 수족관 y좌표에 저장하겠습니다.
이 과정을 왼쪽 → 오른쪽, 오른쪽 → 왼쪽 한 번씩 하겠습니다.
자세한 설명을 위해 먼저 왼쪽에서 오른쪽으로 가는 과정을 보여드리겠습니다.
구멍이 있기 때문에 물의 y좌표가 수족관의 y좌표와 같아졌습니다.
물의 y좌표가 수족관의 y좌표보다 작기 때문에 물을 담을 수 있습니다.
물의 y좌표가 현재 수족관 y좌표보다 크기 때문에 물을 담을 수 없어 물의 y좌표만 변경합니다.
이제 오른쪽에서 왼쪽으로 한 번 더 처리해 주겠습니다.
원래 있던 물의 y좌표보다 물의 y좌표가 더 크기 때문에 값을 변경해 줍니다.
수족관을 구현을 하였으니 이제 남아있는 물의 양의 합을 구하여 출력해 주시면 됩니다!!
(i 번째 가로 선분 왼쪽 x좌표 - i 번째 가로 선분 왼쪽 x좌표) * (i 번째 위치 수족관 y좌표 - 물의 y좌표)
의 합을 구하면 되겠네요!
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define RFOR(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define fs first
#define sd second
using namespace std;
int main() {
FIO;
int n; cin >> n;
pii arr[2505], d[2505];
bool h[2505] = {};
int a, b, c;
cin >> a >> b; n = (n - 1) >> 1;
FOR(i, 0, n - 1) {
cin >> a >> b >> c;
arr[i] = { a,c };
d[i] = { b, 0 };
cin >> c;
}
cin >> a >> b;
auto cmp = [](const pii& a, const pii& b) {
return a.fs < b.fs;
};
int k; cin >> k;
while (k--) {
cin >> a >> b >> c >> b;
int idx = lower_bound(arr, arr + n, pii(a, c), cmp) - arr;
h[idx] = 1;
}
int water = 0;
auto f = [&](int i) {
if (h[i]) water = d[i].fs;
else water = max(min(water, d[i].fs), d[i].sd);
d[i].sd = water;
};
RFOR(i, n - 1, 0) f(i);
water = 0;
FOR(i, 0, n - 1) f(i);
int ans = 0;
FOR(i, 0, n - 1)
ans += (arr[i].sd - arr[i].fs) * (d[i].fs - d[i].sd);
cout << ans << '\n';
return 0;
}