[백준 13334 C++] 철로

오늘은 백준(BOJ) 13334번 철로 문제에 대해 다뤄볼 예정이다.

철로 문제 링크 (백준(BOJ) 13334번 문제): https://www.acmicpc.net/problem/13334

13334번: 철로

문제 설명

백준 13334번 철로 문제는 각 사람 당 집과 사무실의 위치를 입력받은 후, 얼마나 많은 사람이 철도의 길이 L 안에 포함될 수 있는지 출력하는 문제이다. 아래 사진을 예시로 들어보면, L 범위안에 (5, 40)은 범위를 벗어나기에 제외하고, (10,20), (10, 25), (25, 30), (25, 35) 총 4명이 포함될 수 있는 것이다. 

집과 사무실의 위치

문제 풀이

백준 13334번 철로 문제의 핵심은 끝점(사무실의 위치)를 기준으로 오름차순 정렬을 수행하는 것이다. 만일 사무실의 위치가 같을 경우에는 시작점(집의 위치)를 비교하여 오름차순 정렬한다. 그리고, 우선 순위 큐(Priority Queue)를 사용하여 원소를 작은 순서대로 저장하도록 해준다.

 

알고리즘 원리 

1. 끝점을 기준으로 정렬, 끝점이 같을 경우 시작점을 비교하여 정렬 

[반복 2 ~ 5]

2. L 범위내에 존재하는 것들만 큐에 넣기 위해, (끝점 - 시작점)이 L 보다 클 경우, 무시

3. 만일 (끝점 - 시작점)이 L 보다 작을 경우, 우선 순위 큐(Priority Queue)에 시작점을 넣어준다. 

4. 끝점이 (시작 위치, 시작 위치 + L) 범위 안에 존재하는지 확인 후, 범위 안에 있다면 max()를 통해 비교

5. 범위 안에 없는 경우, pop()