문제
https://www.acmicpc.net/problem/13334
접근
- 가장 처음 시도한 방법은 정렬과 스위핑을 사용해서 철도의 구간과 구간에 들어가는 경로의 개수를 갱신해나가는 방법으로 풀이했으나 틀림 -> 반례가 무엇인지 못찾겠다...
- 다른 방법으로 정렬된 전체 경로들(시작점과 끝점이 철도의 길이 d보다 작거나 같은 경로들)에 대해, 철도의 길이 d에 함께 포함될 수 있는 경로들을 따로 저장(q)해놓고, 그 구간을 벗어나는 경로를 만날때마다 새로운 경로에 맞춰 q에 저장한 경로 정보를 갱신하기로 결정
- 갱신할 때마다 경로의 값이 작은 경로들 순으로 비교해야 하므로 우선순위큐를 사용했으나 틀림
- 반례를 통해 전체 경로를 정렬할 때 시작점이 아닌 끝점을 기준으로 정렬해야 함을 깨닫고 수정 후 풀수 있었다.
풀이
- 우선 경로의 길이가 철도의 길이인 d보다 큰 경로들은 빼고 풀이한다.
- 각 (기준) 경로에 대해 우선순위큐 안에 있는 원소들 중 기준 경로와 같은 철도 구간에 포함될 수 있는지 확인 후, 불가능하다면 제거한다.
- 우선순위큐 안에 같이 포함된 원소는 같은 철도 구간에 포함될 수 있다는 뜻이므로, 매 시행마다 ans를 우선순위큐의 길이의 최대값으로 갱신한다.
import heapq
n = int(input())
a = []
for _ in range(n):
s, e = map(int, input().split())
if s > e:
s, e = e, s
a.append((s, e))
d = int(input())
b = [(s, e) for s, e in a if e - s <= d]
b.sort(key=lambda x:x[1])
ans = 0
q = []
for s, e in b:
if not q:
heapq.heappush(q, (s, e))
else:
while q and e - q[0][0] > d:
heapq.heappop(q)
heapq.heappush(q, (s, e))
ans = max(ans, len(q))
print(ans)
'Python > Coding Test' 카테고리의 다른 글
2749 피보나치 수 3 (0) | 2022.02.16 |
---|---|
21939 문제 추천 시스템 Version 1 (0) | 2022.02.16 |
2485 가로수 (0) | 2022.02.14 |
19235 모노미노도미노 (0) | 2022.02.13 |
16960 스위치와 램프 (0) | 2022.02.13 |