[BOJ#23254] 나는 기말고사형 인간이야

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

1 초

1024 MB

865

413

332

48.968%

문제

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

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

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

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

입력

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

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

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

출력

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

제한

•  1≤𝑁,𝑀≤200000$1 \leq N, M \leq 200\,000$ 
•  1≤𝑎𝑖,𝑏𝑖≤100

---

제출 코드

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

# 시험은 24 x N 시간 후, 과목수 M
N, M = map(int, input().split())
time = N * 24
# 기본점수
base = list(map(int, input().split()))
up = list(map(int, input().split()))
heap = []

for i in range(M):
    if base[i] + up[i] > 100:
        up[i] = 100 - base[i]
    heappush(heap, [-up[i], base[i]])


studytime = 0
while studytime < time:
    r, c = heappop(heap)
    c -= r
    if c - r > 100:
        r = c - 100
    heappush(heap, [r, c])
    studytime += 1

result = 0
for i in range(M):
    result += heap[i][1]
print(result)

1. 맥스힙을 사용하기 위해 한시간에 증가하는 점수를 음수로 바꿔서 사용

2. 현재 점수에 한시간에 증가하는 점수가 가장 큰 인덱스부터 팝해와서 더하기

3. 다음 증가했을때 점수가 100을 넘으면 맥스힙을 증가점수-100 으로 바꿔서 다시 푸시 (우선순위 큐 순서를 바꾸기위함)

 

study 시간을 다 썼을때의 결과값 출력 heapq를 쓸 줄 몰라서 다른 분의 코드를 참고했다.