https://www.acmicpc.net/problem/13334
13334번: 철로
입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0
www.acmicpc.net
스위핑 문제다.
풀이
입력되는 구간의 정보를 도착좌표를 기준으로 오름차순으로 정렬한다. 이후 길이가 D 이하인 구간에 대해서만 시작 좌표를 heap에 담아낸 뒤, 매 탐색마다 heap에서 (현재 구간의 도착좌표 - D) 보다 큰 좌표들의 개수를 세면 된다. 해당 값 중 가장 큰 값이 정답이다.
예제를 기준으로 다음과 같이 동작한다.
입력되는 구간을 좌표를 기준으로 오름차순, 도착좌표가 같다면, 출발좌표를 기준으로 오름차순으로 정렬한다.
이후 출발좌표를 담아낼 최소 heap 개수의 최댓값을 정답으로 출력하면 된다.
가장 먼저 탐색할 구간의 도착좌표는 20이며 해당 구간의 길이는 D(30) 보다 작으므로 heap에 해당 구간의 출발좌표인 10을 추가한다.
(도착좌표 - D)의 값이 heap의 peek보다 작으므로 다음 탐색으로 넘어간다.
다음으로 탐색할 구간의 출발좌표는 10이며 해당 구간 또한 크기가 D보다 작고
heap의 peek가 (도착좌표 - D) 보다 크므로 heap에 10을 추가하고 다음 탐색으로 넘어간다.
출발 좌표 25를 담아내고, (도착좌표 - D)의 값이 peek보다 작으므로 다음 탐색으로 넘어간다.
동일하게 출발 좌표 25를 heap에 담아내고 (도착지점 - D)가 5로 현재 peek값 10보다 작으므로 다음 탐색으로 넘어간다.
해당 구간은 길이가 D보다 크므로 아무 작업을 하지 않고 다음 탐색을 이어간다.
해당 구간의 출발 좌표 30을 담아낸다. 여기서 heap의 변화가 일어난다.
(도착지점 - D)의 값이 20이므로 peek 값인 10보다 크다. 따라서 heap에서 20보다 작은 값은 삭제한다.
heap의 크기는 3으로 변경되며 peek값은 25로 갱신되었다.
출발좌표 50을 heap에 담고, (도착지점 - D)의 값인 30보다 작은 값들은 heap에서 삭제.
현재 heap의 크기는 2, peek값은 30이 되었다.
마지막 구간의 출발좌표 80을 담고 (도착지점 - D)의 값인 70보다 작은 값은 모두 heap에서 제거.
heap의 크기는 1이며 peek값은 80으로 변경된다.
탐색동안의 heap의 최댓값인 4를 출력하면 정답이다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [14907] 프로젝트 스케줄링 (0) | 2023.04.03 |
|---|---|
| [2637] 장난감 조립 (0) | 2023.04.01 |
| [3895] 그리고 하나가 남았다 (0) | 2023.03.24 |
| [3770] 대한민국 (0) | 2023.03.14 |
| [3653] 영화 수집 (0) | 2023.03.12 |