[Python] 백준 13334번 철로

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

13334번: 철로

이번에 풀 문제는 철로 문제이다. 문제에서 요구하는 사항은 다음과 같다.

• 집과 사무실을 통근하는 n명의 사람들이 있고, 각각의 사람들의 집의 좌표와 사무실의 좌표가 정보로 주어진다. 
• 설치할 수 있는 철로의 길이 d가 주어진다. 
• 이때 집과 사무실이 모두 철로의 경로에 포함되는 사람의 수를 최대로 하게끔 철로를 설치하는 프로그램을 작성하라. 

문제 풀이

먼저 입력값을 살펴보면, 집의 위치가 항상 사무실보다 왼쪽에 위치하지 않는 것을 볼 수 있다. 따라서 입력값을 받을 때 둘의 대소 관계를 비교하고, 작은 값이 앞에 오게끔 설정해 주었다. 

이 문제 또한 본격적으로 풀기 전에 완전 탐색으로 생각을 해보자. 

• 문제에서는 n명의 사람들에 대한 정보가 주어진다.
• n명중 1명을 선택하여, 선택한 사람의 시작 위치에 철로를 설치한다고 가정한다.
• 나머지 (n-1)명을 조사하며 시작 위치와 끝 위치가 철로의 범위에 들어오는 경우 count 값을 늘려준다.
• (n-1) 명에 대한 조사가 끝났으면 count 값을 최댓값과 비교하여 갱신해 준다.
• 위의 과정을 n명에 대하여 모두 진행한다.

우리가 완전 탐색에서 알 수 있는 점은, 철로가 포함하는 사람의 수가 최대가 되기 위해서는 철로의 시작 또는 끝이 특정 사람의 시작 또는 끝과 같아야 한다는 점이다. 또 특정 사람에 대해 조사를 하지 않으면 예외가 생길 수 있으므로, 모든 사람에 대해 철로를 두는 경우를 조사해봐야 한다. 

이러한 점들을 고려하여 위의 완전 탐색 방식에서 조금 더 효율적인 방법을 생각해 보았다. 

• 입력값인 (시작 위치, 끝 위치)를 (끝 위치)가 오름차순으로 정렬되게끔 최소힙에 삽입한다. 
• 입력을 모두 받고 난 뒤에는 힙에 있는 원소를 하나씩 꺼내가며, 꺼낸 원소의 끝 위치가 철로의 끝이라고 가정한다. 이때 꺼낸 원소는 possible이라는 최소힙에 삽입한다. possible은 (시작 위치)를 기준으로 하는 최소힙이다.
• possible에 있는 원소를 하나씩 꺼내가며 만약 방금 꺼낸 원소가 현재 검사하는 철로의 범위에 해당하지 않으면 cnt 값을 줄이고 힙에서 삭제한다. 
• 만약 현재 possible의 맨 위에 있는 원소가 철로의 범위에 해당하는 원소라면, 그 이후의 원소들은 모두 시작값이 현재 값보다 크기 때문에 철로의 범위에 속한다고 볼 수 있다. 따라서 반복문을 종료한다. 

 

풀이 코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())
office = []

for _ in range(n):
    start, end = map(int, input().split())
    if start > end:
        start, end = end, start
    heapq.heappush(office, (end, start))

d = int(input())

possible = []
res = 0
cnt = 0
while office:
    end, start = heapq.heappop(office)
    if start >= end - d:
        heapq.heappush(possible, (start, end))
        cnt += 1
    while possible:
        s, e = heapq.heappop(possible)
        if s < end - d:
            cnt -= 1
        else:
            heapq.heappush(possible, (s, e))
            break
    res = max(res, cnt)
print(res)