백준 17251번 힘 겨루기

문제 설명

이번 문제는 N명의 참가자들을 나열하고 기준선을 통해 팀이 나눈 다음 각 팀에서 가장 힘쎈 사람이 나왔을 때, 둘 중 더 힘 쎈 사람이 이기게 됩니다.

N 명의 참가자의 힘을 나타내는 정수가 주어질 때, 이길 확률이 더 높은 팀을 구하는 문제입니다.

 

문제 풀이

아이디어

가장 힘 쎈 팀 구하는 방법

기준선이 어디에 있는지에 상관없이 항상 가장 힘이 갖아 쎈 사람이 있는 팀이 이기게 됩니다.

 

가장 힘이 쎈 사람이 한 명일 경우

가장 힘이 쎈 사람의 인덱스를 i라하면, 기준선이 1~i-1일 경우 블루팀이 이기고, i~N-1일 경우 레드팀이 이기게 됩니다.

여기서 두 팀이 이길 확률을 구해보면, 블루팀은 (i-1)/N이고 레드팀은 (N-i)/N입니다.

그러므로 두 팀 중 이길 확률이 높은 팀은 i-1과 N-i 중 큰 수가 이기는 팀이 됩니다.

 

가장 힘이 쎈 사람이 두 명 이상일 경우

가장 힘이 쎈 사람의 인덱스가 i,j,k라고 하면, 기준선이 i~k-1일 경우 두 팀에서 가장 힘 쎈 사람의 힘이 동일하므로 이기는 팀은 없다.

그러므로 무승부가 될 경우를 제외하고 두 팀의 이길 확률을 구하면 됩니다.

 

기준선이 1~i-1일 경우 블루팀이 이기고, k~N-1일 경우 레드팀이 이기게 됩니다.

두 팀의 이길 확률은 블루팀이 (i-1)/N 이고 레드팀이 (N-k)/N이 됩니다.

그러므로 두 팀 중 이길 확률이 높은 팀은 i-1과 N-i 중 큰 수가 이기는 팀이 됩니다.

 

풀이

가장 큰 힘을 가진 사람의 인덱스 저장

반복문을 통해 가장 힘이 쎈 사람의 인덱스를 배열 max_power_index에 저장해줍니다.

가장 힘이 쎈 사람보다 더 쎈 사람이 등장하면 해당 인덱스를 넣어준 배열을 다시 max_power_index에 할당해줍니다.

가장 힘이 쎈 사람과 동일한 힘을 가진 사람이 있다면 max_power_index배열에 해당 인덱스를 넣어줍니다.

 

이길 확률 구하기

블루팀의 이길 확률은 max_power_index[0]이고 레드팀이 이길 확률은 N-max_power_index[-1]-1이 됩니다.

두 팀의 이길 확률을 비교해 이기는 팀을 출력하면 됩니다.

 

 

해결

이번 문제는 기준선에 따라 이기는 팀에 대한 규칙을 찾고 각 팀이 이기는 확률을 구하는 방법을 찾게 되면 쉽게 풀 수 있는 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/17251

17251번: 힘 겨루기

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/17251.py