1017 최종라운드 우승가능자 수 문서 원본 보기

거의 거저주는 수준인데 답 보고야 깨달았음.

<blockquote>n명의 참가자가 1점부터 n점까지 중복없이 얻고, 이를 수회 반복하여 현재까지 총점을 낸다. 한 라운드 더 진행했을 때 최종 우승가능성을 가진 사람은 몇명인가?</blockquote>

얼핏, 다음과 같지 않을까 싶은데,

\( \text{max_score} + 1 \le \text{someone’s_score} + n \)

저기 \(1\)이 문제다. 총점은 중복이 가능하므로, 고득점자가 복수라면 최고점이 (아무리 낮게 잡아도)

\( \text{max_score} + \text{number_of_max_scores} \)가 된다. 

따라서 \( \text{max_score} + \text{number_of_max_scores} \le \text{someone’s_score} + n \) 을 찾아야 한다.

여기서 끝나면 함정이고,

두번째 동점자가 많을 경우 위와 같은 일이 또 벌어진다. 

결국, 마지막 라운드에서 나올 수 있는 가장 최저의 최대값을 찾는 것이 문제인데, 이건 그냥 해보는 수밖에 없다. 

내림차순 sort하고 \([1, 2, 3, \cdots, n]\)을 더한 후 max보는 수 밖에 없음.


<x>*</x><br>
간만에 다시 보니 한눈에 못알아볼 부분이 좀 보이네 ㅎㅎ
<disqus/>