아래 그림 1은 수족관을 앞에서 본 모양이다. 이 수족관에는 물이 가득 차 있다. 만약 수족관 밑바닥(수평선분)에 구멍을 하나 뚫으면, 구멍을 통해 수족관의 물이 빠지게 된다.
그림 1의 수족관의 경계는 4개의 꼭짓점으로 표현된다. 각 꼭짓점의 위치는 세로줄 번호와 가로줄 번호로 나타낸다. 세로줄은 왼쪽에서 오른쪽으로 0번부터 차례로 증가하는 번호를 붙이고, 가로줄은 위부터 아래로 0번부터 차례로 증가하는 번호를 붙인다. 이웃한 두 세로줄 사이의 거리와 이웃한 두 가로줄 사이의 거리는 모두 1이다. 그래서 왼쪽 위에 있는 꼭짓점의 위치는 (세로줄 번호, 가로줄 번호) = (0, 0)이 되고, 이 꼭짓점부터 시계반대방향으로 수족관의 경계를 따라가면서 만나는 꼭짓점들의 위치는 차례로 (0, 5), (8, 5), (8, 0)이 된다.
수족관의 바닥을 나타내는 수평선분에 구멍이 있다면, 그 수평선분이 위치한 가로줄보다 위쪽에 있으면서 중력에 따라 구멍으로 흘러 들어갈 수 있는 위치에 있는 물은 모두 그 구멍을 통해 외부로 배출된다. 따라서 그림 1의 물은 바닥의 구멍을 통해 남김없이 모두 빠진다.
수족관에 담긴 물의 양은 물이 차지하는 면적과 일치하는 양이다. 물의 양의 단위는 L(리터)이다. 따라서 그림 1에서 가득 담긴 물의 양은 물이 차지하는 면적과 동일한 40L이다.
그림 2처럼 수족관의 바닥이 복잡할 수도 있다.
수족관의 바닥은 수평선분과 수직선분이 번갈아 여러 번 나타나는 형태이다. 또한 그림 2처럼 수족관 위에서 수직방향으로 수족관 바닥을 보았을 때, 수족관의 바닥이 모두 보이는 (즉, 모든 수평선분이 보이는) 형태이다.
구멍은 항상 수평선분에만 존재하며, 수평선분의 한 가운데에 위치한다. 그리고 하나의 수평선분에는 최대 하나의 구멍만 존재할 수 있다. 그림 2에는 2개의 구멍(1번 구멍과 2번 구멍)이 있다. 이 구멍들을 통해 물을 빼면, 그림 3과 같이 빠져나가지 못한 물이 7L 남게 된다.
물이 가득 찬 수족관의 바닥 모양과 구멍이 뚫려 있는 수평선분들이 주어지면, 구멍을 통해 물이 빠져 나간 후 수족관에 남아 있는 물의 양이 몇 리터인지 계산하는 프로그램을 작성하시오.
입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(1 ≤ N ≤ 5,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난다. 즉, 시작 꼭짓점과 마지막 꼭짓점의 가로줄 번호는 항상 0이다. 수족관의 경계를 이루는 변은 꼭짓점 (0, 0)부터 시작하는 데, 수직선분으로 시작하여 수평선분과 수직선분이 번갈아가며 반복되다 수직선분으로 끝난다. 따라서 수직선분이 수평선분보다 항상 하나 더 많다. 두 번째 줄부터 N개의 줄에는 수족관 경계에 있는 N개의 꼭짓점의 세로줄 번호와 가로줄 번호가 빈칸을 사이에 두고 각 줄에 하나씩, 첫 꼭짓점 (0, 0)부터 시계반대방향을 따라 차례로 주어진다. 세로줄과 가로줄 번호의 범위는 0 이상 40,000 이하의 정수이다. 다음 줄에는 수족관의 수평선분에 위치한 구멍의 개수 K (1 ≤ K ≤ N/2)가 자연수로 주어진다. 다음 K개의 줄에는 각 구멍이 존재하는 수평선분의 양 끝 꼭짓점 위치를 나타내는 네 개의 값이 빈 칸을 사이에 두고 차례로 주어진다. 즉, 어떤 구멍이 위치한 수평선분의 정보가 a b c b로 주어졌다면, 구멍이 위치한 수평선분은 꼭짓점 (a, b)와 꼭짓점 (c, b)를 연결한 선분이라는 의미이다. 항상 a < c 이다.
출력
출력은 단 한 줄이며, 구멍을 통해 물이 빠져 나간 후, 수족관에 남아 있는 물의 양을 0 이상의 정수로 출력한다.
입력 예시
4
0 0
0 5
8 5
8 0
1
0 5 8 5
출력 예시
0
풀이
python3으로 풀었을 때, 본 시간복잡도와 python의 한계 때문에 마지막 서브태스크에서 시간 초과를 일으키는 것을 확인하였다. pypy3으로는 통과 가능한 코드이며, 조금만 손을 보면(입력 좌표를 일일히 채워 넣었었는데, 범위를 기준으로 하면 좀 더 통과 가능할 것이다) 통과 가능하다.
수족관의 한 구멍을 중심으로, 구멍이 있는 좌표구간은 무조건 0의 물이 남게 된다. 그리고 구멍이 있는 좌표 구간의 깊이를 기준으로 왼쪽과 오른쪽으로 탐색을 해 나가는 것이 핵심이다. 전체 좌표구간을 N, 구멍의 좌표 구간을 K라고 할 경우 O(NK)의 시간복잡도를 가지게 된다(c++이나 더 가벼운 언어였으면 통과하였을 것을...)
깊이가 더 얕은 구간을 만났을 경우 : 기준 깊이를 더 얕은 구간으로 업데이트한다.
앞서 변동된 기준 깊이와 현재 깊이의 차가 현재 탐색을 통해 남는 물이 될 것이다. 현재 남은 물과 여기서 구한 남는 물의 양 중 더 작은 값을 저장한다.
모든 구간에 대해 이를 반복한다.
water_init : 수족관 좌표를 입력받아 현재 n, n+1구간의 물을 저장하는 water_list와 원래 깊이인 depth_list에 저장한다. water_list와 depth_list의 초기값은 같다.
hole_init : 구멍의 좌표를 입력받아 리스트로 반환한다.
sink_water : 앞서 설명한 대로, 하나의 구간 구멍을 입력받아 water_list 전체를 업데이트한다.
full_sink : 모든 hole_list의 구멍들에 대해 sink_water를 호출하여 water_list를 업데이트한다.
solve : 메인함수. water_init과 hole_init을 통하여 리스트를 입력받고, full_sink로 water_list를 업데이트하여 그 합을 출력한다.
풀이 코드
from collections import defaultdict
import sys
input = sys.stdin.readline
def water_init() :
prev_y = -1
N = int(input())
water_list = list()
depth_list = list()
for x, y in [map(int, input().split()) for _ in range(N)] :
if y == prev_y :
for _ in range(x - prev_x) :
water_list.append(prev_y)
depth_list.append(prev_y)
prev_x, prev_y = x, y
return water_list, depth_list
def hole_init() :
K = int(input())
hole_list = [list(map(int, input().split())) for _ in range(K)]
return hole_list
def sink_water(depth_list, water_list, sx, ex, y) :
length = len(water_list)
for x in range(sx, ex) :
water_list[x] = 0
min_sinked = y
for x in range(sx-1, -1, -1) :
min_sinked = min(min_sinked, depth_list[x])
water_list[x] = min(water_list[x], depth_list[x] - min_sinked)
min_sinked = y
for x in range(ex, length) :
min_sinked = min(min_sinked, depth_list[x])
water_list[x] = min(water_list[x], depth_list[x] - min_sinked)
def full_sink(water_list, depth_list, hole_list) :
for sx, y, ex, _ in hole_list :
sink_water(depth_list, water_list, sx, ex, y)
def solve() :
water_list, depth_list = water_init()
hole_list = hole_init()
full_sink(water_list, depth_list, hole_list)
print(sum(water_list))
solve()
