백준 27654 - 시험 (Python)

문제 정보

• https://www.acmicpc.net/problem/27654
• 매개 변수 탐색, 이분 탐색

---

문제 정리

각 시험 i는 $(P_i, Q_i)$로 주어지며, 이는 "총 $Q_i$ 문제 중 $P_i$개 정답"을 의미한다.
시험 집합 $X$의 평균 성적은 다음과 같이 정의된다.

• $\frac{\Sigma{P_x}}{\Sigma{Q_x}}$

전체 N개의 시험 중 정확히 K개를 골라, 위 평균 성적을 최대화해야 한다.

---

풀이

단순하게 개별 정답률이 높은 시험부터 K개를 뽑는 경우 항상 최적해를 보장하지 못한다. 아래 반례를 보자.

3 2
2 4
10 17
15 16

각 시험의 맞은 비율은 0.5, 0.58..., 0.93... 이므로 정답률 내림차순으로 2개를 고르면 두 번째 + 세 번째 시험을 선택하게 되고, 이 경우
$\frac{25}{33} = 0.75...$
가 도출된다. 그러나 첫 번째와 세 번째 시험을 선택한 경우
$\frac{17}{20} = 0.85$
가 되어 앞의 경우보다 더 높은 값이 나온다. 분모가 가중치처럼 작용하기 때문에 단순 그리디로는 풀 수 없다.

결정 문제를 "N개 중 K개의 시험을 적절히 뽑아 평균 성적을 D 이상으로 만들 수 있는가?" 라고 둘 경우, 매개변수 탐색을 통해 D의 최대값을 구할 수 있게 된다. 그럼 이 결정 문제는 어떻게 풀 수 있을까?

$\frac{\Sigma{P_x}}{\Sigma{Q_x}} \ge D$ 을 변형하면,
$\Sigma({P_x - DQ_x}) \ge 0$ 가 된다.
이제 모든 시험을 ${P_x-DQ_x}$을 기준으로 정렬하여 높은 값부터 그리디하게 선택한 뒤, 0 이상인지 체크하면 된다.

[0, 1] 범위에 대한 실수 이분 탐색이므로, 조건을 "반복 횟수가 특정값 이하일 경우 반복"으로 두고 탐색해주면 된다.

---

후기

매개 변수 탐색을 떠올리는 것도 힘들고, 결정 문제를 해결하는 방법을 떠올리는 것도 힘들고...
이게 플래인가

---

코드

# 백준 27654

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


# N개의 시험 중 K개를 뽑아 평균값 ev를 만들 수 있는지 체크
def check(N, K, data, ev):
    data.sort(key= lambda x: (ev*x[1]-x[0]))
    accP = 0
    accQ = 0
    for i in range(K):
        accP += data[i][0]
        accQ += data[i][1]

    if accP/accQ >= ev:
        return True
    return False


def solve(N, K, data):
    yes = 0
    no = 1
    repeatCount = 0
    while repeatCount < 50:
        mid = (yes+no)/2
        if check(N, K, data, mid) == True:
            yes = mid
        else:
            no = mid
        repeatCount += 1

    return yes


def main():
    N, K = map(int, input().split())
    data = []
    for _ in range(N):
        data.append(tuple(map(int, input().split())))
    print(solve(N, K, data))


main()