이번 대회에서 가장 쉬운난이도를 보여준(44팀 성공)문제치고는 정답률(27%) 이 낮았던 문제였습니다.
실제 문제를 읽어보시면 아시겠지만 문제의 서술이 너무 장황했었고(실제로 대회가 끝난다음 Gumx팀의 모분께서 그런 이야기를 하셔서 저도 다시 읽어보니 참 어렵게도 써놨구나라는 생각이 들었습니다. 다음에 출제를 할 경우가 생기면 최대한 쉽게 읽히도록 노력해보겠습니다.), 기존의 A번 문제 치고 난이도가 있었으며(개인적으로 따져본 난이도는 작년도 서울지역 인터넷 예선 B번의 수준의 난이도라고 생각됩니다.), 단순히 직관으로만 증명되지 않는 문제이기 때문에 많은 분들이 실수를 하셨던거 같습니다.
이 문제의 해법은 간단합니다.
남성의 리스트와 여성의 리스트를 각각 오름차순으로 정렬한 다음 순서대로 매치를 하게 되면 최적해가 나오게 됩니다.
이 부분에 대한 증명은 숙제로 남겨두도록 하고 이를 쉽게 구현하기 위한 방법을 설명하겠습니다.
일단 해법을 떠올리게 되면 구현해야할 부분은 2가지로 나오게 되는데, 첫번째로는 리스트를 정렬하는 부분, 두번째로는 두개의 리스트의 차이를 구하는 부분으로 나뉩니다. 두번째 부분의 경우는 단순한 반복문 사용을 통해 구현 되기 때문에 자세한 설명은 생략하기로 하고, 어떻게 정렬을 구현할 것인가에 대해 중점을 두어 이야기하고자 합니다.
리스트 정렬의 경우에는 이번 문제는 N이 최대 10,000이므로 단순하게 구현 가능한 O(N^2)의 정렬의 경우에는 시간제한 초과의 위험을 가지고 있고 실제 대회에서는 이러한 정렬을 이용해 제출된 코드는 제한 시간내에 수행되지 못해 오답을 받았습니다.
하지만 C++이나 Java, 그리고 대부분의 프로그래밍 언어에서는 시간복잡도 O(nlogn)을 보장하는 정렬 라이브러리를 제공합니다. 이를 사용할 경우 제한 시간의 압박에서 벗어 날 수 있습니다. 사용하는 언어의 정렬 함수를 알아두는 것은 실무에서나, 그리고 대회 상에서 큰 도움을 주게 됩니다.
C++에서 STL이 제공하는 std::sort() 함수를 사용하는 방법은 다음과 같은데, 우선 다음과 같은 헤더를 포함시킵니다.

#include <algorithm>

[0,n-1] 범위 내의 a라는 1차원 배열을 정렬하는 방법은 다음과 같습니다.

std::sort(a,a+n);

만약에 vector와 같은 STL 자료구조를 이용하실 경우는 다음과 같은 방법으로 오름차순 정렬이 가능합니다. begin()과 end()는 vector의 반복자(iterator)의 시작과 끝을 의미합니다.

std::sort(a.begin(),a.end());

이를 통해서 완성된 A번의 C++ 해답 코드는 아래와 같습니다.

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    const int MN = int(1e4);
    int tn, n;
    scanf("%d", &tn);
    vector<int> boy;
    vector<int> girl;
    while(tn--) {
        scanf("%d", &n);
        boy.resize(n,0);
        girl.resize(n,0);
        for(int i=0;i<n;++i) scanf("%d",&boy[i]);
        for(int i=0;i<n;++i) scanf("%d",&girl[i]);
        sort(boy.begin(),boy.end());
        sort(girl.begin(),girl.end());
        int ret = 0;
        for(int i=0;i<n;++i) ret += abs(boy[i]-girl[i]);
        cout << ret << endl;
    }
}

Java에 대해서는 제가 조예가 깊지 않기 때문에 이 부분에 대해선 충분한 설명을 드릴 수는 없을것 같습니다. 이 부분에 대해서는 다른 분들의 코멘트를 기다립니다.