[BOJ 1183 // C++] 약속

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1183번 문제인 약속이다.
문제는 아래 링크를 확인하자.

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

1183번: 약속

문제의 조건에서, "오민식 그룹이 N명이고, 오민식 그룹의 원래 약속시간이 배열 S라고 하고, 도착하는 시간을 배열A이라고 하고, 약속을 T시간만큼 미뤘다면, 기다리는 시간의 총합은 abs(S[i]+T-A[i])를 모두 더한 값이 된다."라고 한 부분을 주목하자.

 

S[i] - T[i]는 변하는 값이 아니므로 상수 "-C[i]"로 생각하자. 그러면, 기다리는 시간의 총합은 abs(T-C[i])가 된다.

 

T가 1 늘어나면 총합은 T>C[i]인 개수만큼 시간의 총합이 늘어나고, T<C[i]인 개수만큼 시간의 총합이 줄어든다.

마찬가지로, T가 1 감소하면 T>C[i]인 개수만큼 시간의 총합이 감소하고, T<C[i]인 개수만큼 시간의 총합이 늘어난다.

 

위 내용을 잘 생각하면, N이 홀수일 경우 T가 정렬된 C값들 중 중앙값인 경우 하나, 짝수일 경우 정렬된 C값들 중 가운데 두 값 사이(경계값 포함)의 수의 개수가 답이 될 것임을 알 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;

int arr[10000];

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		arr[i] = x - y;
	}
	sort(arr, arr + N);
	if (N & 1) cout << 1;
	else cout << arr[N / 2] - arr[N / 2 - 1] + 1;
}