백준 15997문제 승부 예측

문제

카카오 본선 첫번째 문제였다.
4개의 팀이 입력되고, 한 팀은 자신을 제외한 모든 상대방과 한 번씩, 총 3번의 경기를 치른다.
경기의 승자는 승점 3점을 받고 비기는 경우 서로 승점 1점을 받는다. 지는 경우에는 승점을 받지 않는다.
조별리그를 모두 치른 후 승점 순으로 순위를 정하는데 승점이 같을 시에는 추첨으로 순위를 정하며, 추첨은 공평하게 진행된다. 순위를 정한 후 상위 2팀은 다음 라운드로 진출한다. 진출할 확률을 계산해내는 문제이다.

입력값 예시
KOREA CCC BBB AAA
KOREA CCC 1.0 0.0 0.0
AAA BBB 0.428 0.144 0.428
AAA KOREA 0.0 0.0 1.0
CCC BBB 0.0 0.0 1.0
KOREA BBB 1.0 0.0 0.0
CCC AAA 0.0 0.0 1.0

출력값 예시
1.0000000000
0.0000000000
0.5000000000
0.5000000000

접근법

이 문제를 어렵게 만드는것은 2가지이다.
하나는 DFS방식을 생각한 고려법 ( 뒤로 돌아가지 않는다. 왜? 이미 어떤 경기가 일어난다는 가능성이 고려된 문제이기 때문이다. ), 둘째는 확률의 확률이라는 문제이다.
이 둘째 문제를 어떻게 접근하는가가 아주 핵심적인 문제인데, 이 문제는 두가지의 확률을 가지고 풀어야한다.
1. 이 경기가 일어날 확률
2. 결국 팀이 진출할 확률
경기가 일어나는 확률은 보통 DFS문제에서 아래로 내려주는 형태로 이루어지기 때문에, DFS 문제라는것만 생각해내면 경기가 일어날 확률은 구하는게 어렵지 않다.

        double deptPercent = percent * rate[row][column];

해당 코드를 통해 나는 1을 아래로 계속 내려주면서, 이 경기의 확률을 어렵지 않게 계산해냈다.
그렇다면 여기까지가 쉬운 접근이라면, 이제 문제는 결국 팀이 진출할 확률이다.

풀이법

사실 고민을 가장 많이 한 부분이다.
아래로 내려주면서 어떤 한 경우의 수의 문제와 그 값은 구해냈는데, 결국 최종 계산값을 구해내기가 굉장히 힘들었는데, 이 문제의 키포인트는 1등과 2등의 개수를 세고, 1등이 2명 이상일 경우, 2등은 확률에서 제외해내는것이다.
즉, 1등이 1명일때와 1등이 2명 이상일때 2가지로 나누면 굉장히 쉽다.

if (sorted[0] == score[i]) {
	result[i] += (deptPercent * (first == 1 ? 1.0 : 2.0 / first));
}
if (first == 1 && sorted[1] == score[i]) {
	result[i] += (deptPercent / second);
}

여기서 sorted는 정렬한 배열이고, score는 처음 받는 팀들의 점수이다.
이것이 i값이 맞아야지만 제대로 팀 이름에 접근할 수 있어서 처음 if문이 존재한다.
그러면 핵심적인 뒷내용을 보자. 만약 first가 1명이면 2등은 계산 경우에 들어가지만, 그렇지않으면 들어가지 않는다. 이것이 sorted[0]을 보느냐 [1]을 보느냐의 차이를 이뤄낸다.
결국 결과 확률값은 (이 경우가 일어날 확률 X 2/일등의 갯수) 이거나, (이 경우가 일어날 확률 X 2등의 갯수)이다.