BOJ 28449 : 누가 이길까

• 문제 링크 : boj.kr/28449
• 난이도 : G5
• 태그 : 누적합

28449번: 누가 이길까

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n, m;
    cin >> n >> m;
    vector<ll> a(100001), b(100001);
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        a[input]++;
    }
    for(int i = 0; i < m; i++) {
        int input;
        cin >> input;
        b[input]++;
    }
    for(int i = 1; i <= 100000; i++) {
        a[i] += a[i-1];
        b[i] += b[i-1];
    }

    ll wa, wb, d;
    wa = wb = d = 0;

    for(int i = 1; i <= 100000; i++) {
        ll ak, bk;
        ak = a[i] - a[i-1];
        bk = b[i] - b[i-1];
        wa += ak * b[i-1];
        wb += bk * a[i-1];
        d += ak * bk;
    }
    cout << wa << " " << wb << " " << d;

    return 0;
}

---

풀이

K점인 어떤 사람은 상대팀의 K점인 사람 수만큼 비기고, K점보다 낮은 사람 수만큼 이긴다.

위의 문장을 그대로 구현하면 된다.

 

점수의 최댓값이 100000이니, 카운팅정렬을 사용할 수 있다. 카운팅정렬 후 누적합을 이용해주면 K점 이하인 사람 수를 쉽게 구할 수 있다. 이를 K점인 사람과 K보다 낮은 사람으로 나누어 구하면 된다.