cotton 블로그 cotton 블로그

백준 17251번 힘 겨루기

• 백준 17251번 힘 겨루기

  알고리즘 2023. 3. 6. 10:42

  문제 설명 이번 문제는 N명의 참가자들을 나열하고 기준선을 통해 팀이 나눈 다음 각 팀에서 가장 힘쎈 사람이 나왔을 때, 둘 중 더 힘 쎈 사람이 이기게 됩니다. N 명의 참가자의 힘을 나타내는 정수가 주어질 때, 이길 확률이 더 높은 팀을 구하는 문제입니다. 문제 풀이 아이디어 가장 힘 쎈 팀 구하는 방법 기준선이 어디에 있는지에 상관없이 항상 가장 힘이 갖아 쎈 사람이 있는 팀이 이기게 됩니다. 가장 힘이 쎈 사람이 한 명일 경우 가장 힘이 쎈 사람의 인덱스를 i라하면, 기준선이 1~i-1일 경우 블루팀이 이기고, i~N-1일 경우 레드팀이 이기게 됩니다. 여기서 두 팀이 이길 확률을 구해보면, 블루팀은 (i-1)/N이고 레드팀은 (N-i)/N입니다. 그러므로 두 팀 중 이길 확률이 높은 팀은 i-1..

  Read More