[백준 13334] 철로

13334번: 철로

이 문제가 원래 우선순위 큐를 두개로 푸는게 정석이라는데 아마 이 문제 컨셉이 보석 도둑과 비슷한가 봅니다. 근데 저는 머리가 안좋아서 보석 도둑을 풀었을 때의 풀이법은 다 까먹었고, 다른 방법으로 풀었습니다. 저 "보석 도둑"도 시간 나면 복기해봐야겠군요.

 

아까도 얘기했지만 정석과 다르게 우선순위 큐를 하나만 썼습니다. 하나만 쓸 수 있었던게 가능했던 이유는 구간 집-사무실 사이의 구간 P(h, o)를 P를 포함하게 깔을 수 있는 철로의 시작점의 범위 P'(o-L, h)로 바꾼 다음 가장 많이 겹치는 P'의 갯수를 구했기 때문입니다. 즉, 특정 지점 x에 철로를 깔았을 때, 이 x를 포함하는 P'의 갯수가 곧 철로 L이 포함할 수 있는 P의 갯수가 됩니다.

 

P'(o-L, h)의 집합을 구했으면 o-L이 작은 순으로 정렬한 다음 P'의 배열을 순회하면서, 우선순의 큐를 이용해 가장 겹치는 P'의 갯수를 구하면 됩니다.

우선수위 큐의 데이터 요소는 P'의 끝지점, 데이터의 길이는 겹치는 P'의 갯수가 되고, 정렬 조건은 오름차순이 됩니다.

P'가 새로 들어올 때마다 P'의 시작 지점이 우선수위 큐 안의 요소보다 작을 때 까지 제거합니다. 어떤 P'의 시작 지점이 우선 순위 안의 P'의 끝지점 보다 더 크면 서로 겹치지 않기 때문입니다. 제거가 다 끝나면 새로운 P'를 우선순위 큐에 집어넣고 그 큐의 길이를 구합니다. 이렇게 구한 우선순위 큐의 길이값 중 가장 큰 값이 정답이 됩니다.

 

코드 보기 (Python)

import sys
import heapq
input = sys.stdin.readline

n = int(input())
_a, a = [], []
ans = 0
H = []

# input
for _ in range(n):
    h, o = map(int, input()[:-1].split())
    _a.append([h, o])
L = int(input())

# o-L, h로 치환
for h, o in _a:
    if o < h:
        h, o = o, h
    if o - h <= L:
        a.append((o-L, h))
# 정렬
a.sort(key=lambda e: (e[0], e[1]))
# 겹치는 부분 갯수 구하기
for h, o in a:
    
    while H and H[0] < h:
        heapq.heappop(H)
    heapq.heappush(H, o)
    ans = max(ans, len(H))

print(ans)

P'로 치환만 하면 사실 상 이 문제와 일치합니다.

11000번: 강의실 배정