[Baekjoon 12683] Test Passing Probability (Small) | Python

https://www.acmicpc.net/problem/12683

---

문제

 

각 문제의 정답 확률과 답안 제출 기회를 사용하여 답안을 제출했을 때 모든 문제를 맞아 시험에 합격할 수 있는 확률의 최댓값을 구하는 문제이다.

영어 문제이지만, 번역기 정도만 사용해도 이해할 수 있다.

 

---

풀이

 

답안 제출 기회에 따라 풀이가 달라질 것이다. 만약 답안 제출 기회가 단 한 번만 있을 경우, 문제를 풀 때 합격 확률이 가장 높은 답안을 선택하여 제출해야 한다. 이 답안의 합격 확률은 각 문제의 정답 확률들을 곱했을 때의 값 중에서 가장 큰 값이 되며, 따라서 이 답안은 각 문제의 정답 확률 중에서 가장 높은 값들이 선택된 답안이 된다.

하지만 답안 제출 기회가 여러 번 있을 경우에는 단순하게 접근하기가 어려워진다. 처음 답안을 제출할 때는 이미 합격 확률이 가장 높은 답안을 제출하였기 때문에, 그 다음 제출할 때는 처음 답안보다 합격 확률이 낮거나 같을지라도, 제출할 수 있는 모든 답안 중에서는 가장 합격 확률이 높은 답안을 선택해야 한다.

처음 제출할 때 가장 합격 확률이 높은 답안을 고르는 것은 각 문제의 정답 확률이 가장 높은 것을 선택하면 되므로 간단하지만, 그 후의 답안들은 간단하게 구할 수 없다. 예를 들어, 주어진 케이스가 다음과 같다고 가정하자.

문제 1의 정답 확률: 0.5, 0.4, 0.1, 0

문제 2의 정답 확률: 0.4, 0.3, 0.2, 0.1

그렇다면 처음 답안의 합격 확률은 각 문제의 가장 높은 정답 확률을 곱한 0.5 * 0.4 = 0.2가 되겠지만, 그 다음으로 합격 확률이 높은 답안은 0.4 * 0.4와 0.5 * 0.3을 비교하여 더 높은 합격 확률을 가진 답안을 제출해야 한다.

따라서 특정한 값을 선택하는 알고리즘을 짜는 것보다는 모든 경우의 수를 구하여 제출 가능한 답안들의 합격 확률을 확인하는 것이 효율적이다. 합격 확률을 확인한 후, 가장 높은 것부터 차례대로 제출 기회를 소비하여 제출하면 된다.

모든 경우의 수를 구하기 위해 순열과 조합 계산을 지원하는 itertools 라이브러리를 사용하였다.

모든 경우의 수 구했다면 이를 하나의 리스트에 담고, 정렬한다. 답안 제출 기회를 모두 소비할 때 최대 시험 합격 확률을 구하기 위해 각 답안을 제출했을 때 정답 확률이 가장 큰 값들을 더해주어야 한다. 따라서 정렬된 모든 경우의 수 리스트를 슬라이싱하여 가장 큰 값들을 추려내고, 남은 것을 모두 더하면 된다.

 

---

코드

 

import sys
from itertools import product

test = int(sys.stdin.readline().rstrip())
for test_num in range(1, test+1):
    submission_n, question_n = map(int, sys.stdin.readline().rstrip().split())
    question_p = []
    all_p = []
    for _ in range(question_n):
        question_p.append(map(float, sys.stdin.readline().rstrip().split()))
    for combinaion in product(*question_p):
        product_p = 1.0
        for prob in combinaion:
            product_p *= prob
        all_p.append(product_p)
    all_p.sort(reverse=True)
    all_p = all_p[0:submission_n]
    ans = sum(all_p)
    print(f'Case #{test_num}: {ans:.6f}')