짤 출처 붐붐붐 내 심장이 뛰네

BOJ 28250 - 이브, 프시케 그리고 푸른 MEX의 아내 링크
(2023.07.19 기준 S2)

문제

$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \textrm{mex}(\{A_i, A_j\})$ 

mex(S)는 집합 S에 포함되지 않은 가장 작은 음이 아닌 정수라고 정의할 때, 주어지는 N개의 정수 수열 A의 위의 식에 대한 값 출력

알고리즘

생각이 필요한 조합론 문제

풀이

문제를 잘 해석해보자.
Ai, Aj = 12345, 67890 이라면 mex({Ai, Aj}) = 0 이다.
Ai, Aj = 0, 13579 이라면 mex({Ai, Aj}) = 1 이다.
Ai, Aj = 1, 0 이라면 mex({Ai, Aj}) = 2 이다.
Ai, Aj = 0, 0 이라면 mex({Ai, Aj}) = 1 이다.

정리하면, 0끼리 만나면 1, 0과 1이 만나면 2, 0과 2 이상이 만나면 1, 1 이상 둘이 만나면 0이다.

원소 인덱스의 중복이 허용되지 않으므로, 결국 이 문제는 원소 조합이다.
예제 1번을 정렬하여 살펴보면
이와 같이 계산된다.

그러니깐 결국은
0의 개수, 1의 개수, 2 이상의 개수를 계산하여,
0끼리 조합, 0과 1의 조합, 0과 2 이상의 조합의 경우의 수를 모두 더하면 정답이 된다.
(물론, 0과 1의 조합엔 2를 곱해야 한다. mex({0, 1}) = 2이니깐)

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll nC2(int n){
    return (ll)n * (n - 1) / 2;
}

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

    int N; cin >> N;
    int A[N]; for (int i = 0; i < N; i++) cin >> A[i];

    // 0, 1, 2 이상을 세자.
    int ct[3] = {0, 0, 0};
    for (int i = 0; i < N; i++) ct[min(A[i], 2)]++;

    // 0끼리의 조합, 0과 1의 조합, 0과 2 이상의 조합의 경우의 수를 계산
    cout << nC2(ct[0]) + (ll)ct[0] * ct[1] * 2 + (ll)ct[0] * ct[2];
}

• Python

import sys; input = sys.stdin.readline

def nC2(n):
    return n * (n - 1) // 2

N = int(input())
A = list(map(int, input().split()))

# 0, 1, 2 이상을 세자.
ct = [0] * 3
for a in A:
    ct[min(a, 2)] += 1

# 0끼리의 조합, 0과 1의 조합, 0과 2 이상의 조합의 경우의 수를 계산
print(nC2(ct[0]) + ct[0] * ct[1] * 2 + ct[0] * ct[2])

여담

난이도 기여에서 드립치려고 했는데....이건 못이기겠다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ