[BOJ 23386] Lopsided Lineup

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

 

플래티넘 1의 수문장 사수아탕이 있다면

플래티넘 3의 수문장은 Lopsided Lineup이라고 생각한다.

진짜 접근을 못하면 몇시간이 저세상으로... ㅋㅋ ㅠㅠ 랜덤 영어 플래 디펜스 하는 중 가장 어려웠던 문제 같다.

 

사실 이것도 나랑 red1108이 올려놓은 난이도다.. 도대체 이걸 처음 준 사람은 왜 플5를 준 것일까..

 

문제

짝수인 $n$에 대해 $n \times n$ 크기의 대칭행렬 $c_{i,j}$가 있다. $c_{i,j}$가 의미하는 것은 $i$번째 사람과 $j$번째 사람이 같은 팀일 때 해당 팀의 점수?같은 것이 $c_{i,j}$만큼 상승한다는 것이다. 사람 수가 같도록 팀을 두 개로 나눌 때, 두 팀의 점수 차이를 최대화하는 방법은?

 

풀이

$n$명 중에 $k$명이 하나의 팀이라고 생각해보자. 행렬을 적당히 바꿔서 $k$명이 $1 \sim k$행과 열을 차지하도록 바꾼다고 생각하자. 그러면 행렬에서 $[1, k] \times [1, k]$의 합은 $k$명이 골라진 팀의 점수(의 두 배)이고, $[k+1, n] \times [k+1, n]$의 합은 나머지 $n-k$명의 사람이 골라진 팀의 점수(의 두 배)이다. $k=n/2$일 때 두 차이를 최대화시키면 된다.

 

여기서 대칭행렬임에 주목하자. $[k+1, n] \times [1, k]$의 합과 $[1, k] \times [k+1, n]$의 합은 같다. 때문에, 정말 놀랍게도, 두 팀의 점수 차이는 $[1, k] \times [1, n]$의 합과 $[k+1, n] \times [1, n]$의 합의 차이와 동일하다. 즉, 굳이 $n/2$명씩 나누지 않더라도, 일반화하여 $k$명과 $n-k$명의 그룹으로 나눈다고 할 때 두 그룹 점수 차이의 최댓값은 행의 합이 큰 순서대로 $\max(k, n-k)$개의 행의 합에서 행의 합이 작은 순서대로 $\min(k, n-k)$개의 합을 뺀 것이다!

 

따라서 각 행의 합과 전체합을 구하고, 각 행의 합을 정렬한 뒤 앞 $n/2$개의 합을 전체합의 절반에서 빼면 답이다. 큰 것 $n/2$개를 더하고 작은 것 $n/2$개를 빼도 된다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

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

    int n;
    cin >> n;
    vector <ll> a(n);
    ll sum = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            ll u;
            cin >> u;
            a[i] += u;
        }
        sum += a[i];
    }
    sum /= 2;
    sort(all(a));
    for(int i = 0; i < n / 2; i++) sum -= a[i];
    cout << sum;
}