문제 링크 백설공주와 난쟁이와 비슷한 것도 같다. 물론 안 풀어봤다. 아무튼 이 문제는 랜덤 알고리즘으로 푸는 문제이다. 처음 접하는 컨셉이라 신선하고 좋다. 문제 요약 길이 $N$의 정수 sequence $A$가 주어진다. 이 때 $A$의 각 원소는 distinct하다. 자연수 $M\in [3,10^9]$을 골라 모든 $A_i$에 대해 $\mathrm{mod\ } M$을 취해줬을 때, $A$의 majority가 존재하게 하는 $M$을 찾아라. 제한 $1\le N\le 5\ 000$ $1\le A_i\le 10^9$ 문제 풀이 Monte Carlo algorithm은 적당한 시간 내에 동작하지만, 확률적으로 정답을 구하지 못할 수 있는 알고리즘을 말한다. 시간이 충분히 빠르다면 여러 번 수행함으로서 정답..