약속
면접 대비시간 제한2초메모리 제한128 MB
N개의 약속 시간과 도착 시간이 주어질 때, 총 대기 시간을 최소화하는 정수 이동 T의 개수를 구하는 문제로 차이값의 중앙값 개수를 세는 방식으로 풀립니다.
문제
마법사 N명이 머글 문화를 이해하기 위해 각자 한 명의 머글과 약속을 잡았다. 마법사는 약속 시간보다 일찍 도착할 수도 있고 늦게 도착할 수도 있으므로, 모든 약속 시간을 같은 정수 T만큼 조정하려고 한다.
한 약속의 기다리는 시간은 먼저 도착한 사람이 상대가 도착할 때까지 기다리는 시간이다. 마법사들의 원래 약속 시간은 A_1, A_2, ..., A_N이고, 도착 시간은 B_1, B_2, ..., B_N이다. 모든 약속 시간을 T만큼 조정하면 기다리는 시간의 합은 |A_i + T - B_i|의 합이 된다.
기다리는 시간의 합이 최소가 되는 서로 다른 정수 T의 개수를 구하자.
입력
첫째 줄에 N이 주어진다.
다음 N개의 줄에는 두 정수 A_i, B_i가 주어진다.
출력
기다리는 시간의 합이 최소가 되는 서로 다른 정수 T의 개수를 출력한다.
제한
- 1 <= N <= 50
- 1 <= A_i, B_i <= 10^9