4. 백준 C++[1183] 약속

[1183] 약속

---

 

난이도: Silver 5

시도횟수: 2

www.acmicpc.net/problem/1183

문제

캠프에는 두 그룹이 있다. 한 그룹은 오민식을 중심으로 모인 그룹이고, 또다른 그룹은 오영식을 중심으로 모인 그룹이다.

오민식 그룹에 있는 사람들은 오영식 그룹에 있는 사람들을 만나기로 약속했다. 오민식 그룹에 있는 각각의 사람들은 정확하게 한 명의 오영식 그룹의 사람들을 만나야 한다. 이때, 오민식 그룹의 i번째 사람은 오영식 그룹의 i번째 사람을 만나야 한다.

불행하게도, 오민식 그룹의 사람들 중 몇 명은 만나기로 약속한 시간에 오영식 그룹의 사람을 만날 수 없다는 것을 알았다. 그들은 너무 빨리 도착하거나 너무 늦게 도착할 것이다.

기다리는 시간의 총 합을 최소화하기 위해서, 오민식 그룹의 사람들은 어떤 시간만큼 약속 시간을 늦추기로 했다. 총 기다리는 시간은 오민식 그룹의 사람이 오영식 그룹의 사람이 나타나기를 기다리는 시간과 오영식 그룹의 사람이 오민식 그룹의 사람이 나타나기를 기다리는 시간을 포함한다. 오영식 그룹의 사람은 조정된 약속 시간에 정확하게 나타날 것이다.

오민식 그룹의 사람이 오영식 그룹의 사람을 만나기로 한 원래 약속시간이 주어지고, 오민식 그룹의 사람이 도착하는 시간이 주어진다.

예를 들어, 오민식 그룹이 N명이고, 오민식 그룹의 원래 약속시간이 배열 S라고 하고, 도착하는 시간을 배열A이라고 하고, 약속을 T시간만큼 미뤘다면, 기다리는 시간의 총합은 abs(S[i]+T-A[i])를 모두 더한 값이 된다.

기다리는 시간의 합이 최소가 되는 T의 개수가 몇 개인지 구하는 프로그램을 작성하시오. T는 음수일 수도 있다.

 

---

제출한 코드

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


int main() {

	int N;
	cin >> N;
	vector<int> arr;
	for (int i = 0; i < N; i++) {
		int min, young;
		cin >> min >> young;
		arr.push_back(min - young);
	}
	sort(arr.begin(), arr.end());
	if (N % 2 == 1) {
		cout << 1;
	}
	else {
		cout << arr[N / 2] - arr[N / 2 - 1] + 1;
	}


	return 0;
}

 

오랜만에 백준을 푸니까 많이 고민하고 풀었다. 

메인 포인트는 절댓값의 합이 최소가 되도록하는 어떤 수 T가 몇개인지 확인하는 것이다.

1학기에 통계학에서 제곱의 합을 최소로하는 선형회귀를 배워서 혹시 그건가 하고 한참 통계학 자료를 뒤적였다.

결국 구글링해서 절댓값 합 최소가 되는 것이 중간값임을 알아냈다 ... ㅠ

 

근데 왠지 기시감이 들어서 왜인지 확인해보니...

  2020학년도 카이스트에서 본 입학 면접 시험이었다 ㅋㅋㅋㅋㅋ

심지어 그때는 잘 풀었던걸로 기억한다. 과거의 나보다 퇴보한게 느껴진다. 그때 교수님이 n이 홀수와 짝수일 떄는 잘 확인하라고 했던 거까지 기억이 난다.

 

  그 당시에는 저 시그마를 하나의 구분구적법으로 보고 적분의 값이 최소가 되는 것이 양쪽 구간의 길이가 같을 때, 즉 중간값임을 대충 증명한걸로 기억한다. 어떻게 그런 생각을 하는지 참

 

그래서 홀수일 때는 중간값이 1개니까 T의 개수는 1, 짝수일 때는 n/2이하 n/2-1이상의 모든 정수가 T의 값이 된다. 

 

코딩은 그냥 각 약속시간 차이를 vector에 저장하고, sort algorithm을 쓴 뒤, 그냥 N의 홀/짝 여부에 따라서 출력해주도록 구현했다. 

 

고등학교때 한걸 복기하려고 한번 써봤다.