[백준 1183] 약속 (C++)

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

문제

---

마법사 N명이 머글 문화를 이해하기 위해 머글과 약속을 잡았다. 각 마법사는 한 명의 머글을 만날 예정이다. 하지만, 마법사는 약속 시간보다 빨리 또는 늦게 도착할 수 있기 때문에 고민에 빠졌다. 결국 기다리는 시간을 최소화 하기 위해 모든 약속 시간을 T씩 미루려고 한다. 기다리는 시간은 먼저 도착한 사람이 늦게 도착한 사람이 도착할 때까지 기다리는 시간을 의미한다.

마법사의 약속 시간은 A₁, A₂, ..., A_N이고, 도착 시간은 B₁, B₂, ..., 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⁹

문제 풀이

---

수학 문제.

 

N의 값이 홀수일 때와 짝수일 때 구하는 방법이 다르다. 홀수라면 최솟값은 모든 

Bi - Ai를

 정렬했을 때의 중앙값이 되며, 짝수는 가운데 두 수 사이의 범위가 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	int A, B;
	cin >> N;
	vector<int> v;
	for (int i = 0; i < N; i++)
	{
		cin >> A >> B;
		v.push_back(B - A);
	}
	sort(v.begin(), v.end());
	if (N % 2 == 0)
	{
		int mid = N / 2 - 1;
		cout << v.at(mid+1) - v.at(mid) + 1 << "\n";
	}
	else
	{
		cout << 1 << "\n";
	}
	return 0;
}