"1017 최종라운드 우승가능자 수"의 두 판 사이의 차이
ph
잔글 |
잔글 |
||
| (같은 사용자의 중간 판 3개는 보이지 않습니다) | |||
| 15번째 줄: | 15번째 줄: | ||
여기서 끝나면 함정이고, | 여기서 끝나면 함정이고, | ||
| − | 두번째 동점자가 많을 경우 위와 같은 일이 벌어진다. | + | 두번째 동점자가 많을 경우 위와 같은 일이 또 벌어진다. |
결국, 마지막 라운드에서 나올 수 있는 가장 최저의 최대값을 찾는 것이 문제인데, 이건 그냥 해보는 수밖에 없다. | 결국, 마지막 라운드에서 나올 수 있는 가장 최저의 최대값을 찾는 것이 문제인데, 이건 그냥 해보는 수밖에 없다. | ||
| − | sort하고 \([1, 2, 3, \cdots, n]\)을 더한 후 max보는 수 밖에 없음. | + | 내림차순 sort하고 \([1, 2, 3, \cdots, n]\)을 더한 후 max보는 수 밖에 없음. |
| + | |||
| + | |||
| + | <x>*</x><br> | ||
| + | 간만에 다시 보니 한눈에 못알아볼 부분이 좀 보이네 ㅎㅎ | ||
| + | <disqus/> | ||
2017년 11월 9일 (목) 09:27 기준 최신판
거의 거저주는 수준인데 답 보고야 깨달았음.
n명의 참가자가 1점부터 n점까지 중복없이 얻고, 이를 수회 반복하여 현재까지 총점을 낸다. 한 라운드 더 진행했을 때 최종 우승가능성을 가진 사람은 몇명인가?
얼핏, 다음과 같지 않을까 싶은데,
\( \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보는 수 밖에 없음.
간만에 다시 보니 한눈에 못알아볼 부분이 좀 보이네 ㅎㅎ