백준 온라인 저지, 그리디 / 23254번: 나는기말고사형인간이야 (파이썬 / 백준 골드문제)

문제

중간고사를 시원하게 망친 찬우는 오늘부터 1분도 쉬지 않고 기말고사 공부에 매진하기로 다짐했다.

기말고사는 정확히 $24\times N$시간 이후에 시작되며, 쉬는 시간 없이 하루에 모든 과목의 시험을 보기 때문에 찬우는 $24\times N$시간동안 공부할 수 있다. 기말고사를 보는 과목은 총 $M$개로, 시험 시간이 빠른 과목부터 각각 $1$부터 $M$까지의 번호가 매겨져 있다. 모든 과목의 최저점은 $0$점, 최고점은 $100$점이다.

찬우는 공부를 하나도 하지 않아도 $i$번 과목에서 $a_{i}$ 점을 받을 수 있으며, $i$번 과목을 정확히 한 시간 공부할 때마다 그 과목의 성적을 $b_{i}$점 올릴 수 있다. 하지만 $i$번 과목을 30분 공부한다고 $\frac{b_{i}}{2}$점이 오르지는 않으며, 아무리 공부하더라도 한 과목에서 최고점인 $100$점이 넘는 점수를 받을 수는 없다. 

모든 과목의 점수의 합이 찬우의 최종 성적이 된다. 높은 성적을 받기 위한 최적의 전략으로 공부할 때, 찬우가 받을 수 있는 최종 성적의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다.

둘째 줄에는 정수 $a_{1}$, $a_{2}$, ..., $a_{M}$이 공백으로 구분되어 주어진다.

셋째 줄에는 정수 $b_{1}$, $b_{2}$, ..., $b_{M}$이 공백으로 구분되어 주어진다.

출력

첫째 줄에 찬우가 받을 수 있는 최종 성적의 최댓값을 출력한다.

제한

• $1 \leq N, M \leq 200\,000$
• $1 \leq a_{i}, b_{i} \leq 100$

예제 입력 1

1 2
50 60
4 3

예제 출력 1

194

24시간 동안 두 과목을 모두 12시간씩 공부하면 1번 과목은 98점, 2번 과목은 96점을 받게 된다.

이때 찬우의 최종 성적은 194점이 되며, 과목별 공부시간을 어떻게 조절해도 194점보다 높은 성적을 받을 수는 없다.

예제 입력 2

8 7
30 15 70 50 40 40 50
2 2 1 3 1 2 1

예제 출력 2

627

192시간 동안 1번 과목을 35시간, 2번 과목을 43시간, 3번 과목을 30시간, 4번 과목을 17시간, 5번 과목을 37시간, 6번 과목을 30시간동안 공부하면 1, 2, 3, 4, 6번 과목은 100점, 5번 과목은 77점, 7번 과목은 50점을 받게 된다. 이때 찬우의 최종 점수는 627점이 되며, 과목별 공부시간을 어떻게 조절해도 627점보다 높은 성적을 받을 수는 없다.

예제 입력 3

1 1
100
1

예제 출력 3

100

힌트

접근 방법

- 각 과목마다 기대값을 통해 최대 점수를 계산한다.
- 0. 각 과목 당 공부해서 더 높은 점수를 얻는 과목 순으로 최대 힙 정렬을 한다.
- 1. 최대 힙에서 원소를 하나씩 뺀 뒤, 기댓값과 최댓값을 고려해 나머지가 발생하지 않는 선까지 점수를 더해주고, 기대값을 남은 점수로 바꾼다.
- 2. n이 0이 되거나 최대 힙의 첫 원소의 점수가 만점인 경우에 탐색을 종료하고 최종 성적의 최댓값을 출력한다.

코드

# https://www.acmicpc.net/problem/23254
# 접근 방법
# 각 과목마다 기대값을 통해 최대 점수를 계산한다.
# 0. 각 과목 당 공부해서 더 높은 점수를 얻는 과목 순으로 최대 힙 정렬을 한다.
# 1. 최대 힙에서 원소를 하나씩 뺀 뒤, 기댓값과 최댓값을 고려해 나머지가 발생하지 않는 선까지 점수를 더해주고, 기대값을 남은 점수로 바꾼다.
# 2. n이 0이 되거나 최대 힙의 첫 원소의 점수가 만점인 경우에 탐색을 종료하고 최종 성적의 최댓값을 출력한다.
import sys, heapq
input = sys.stdin.readline
n, m = map(int, input().split())
subject_score = list(map(int, input().split()))
subject_plus = list(map(int, input().split()))
subject = []
for i in range(m):
    heapq.heappush(subject, [-subject_plus[i], subject_score[i]])
n *= 24
while subject[0][0] != 0 and n > 0:
    x = heapq.heappop(subject)
    p, s = -x[0], x[1]
    quotient = (100 - s) // p  
    if n >= quotient:
        n -= quotient
    else:
        quotient = n
        n = 0
    s = quotient * p + s
    p = 100 - s
    heapq.heappush(subject, [-p, s])
score = 0
for x in subject:
    score += x[1]
print(score)