[Python/파이썬] - 백준(BOJ) 23254번 : 나는 기말고사형 인간이야

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

23254번: 나는 기말고사형 인간이야

 

우선순위 큐 이용하는 그리디 문제.

 

1시간 공부하면 점수가 x점 늘어나는 것을 인덱스별로 저장하기 위해 plus 배열을 생성한다.

높은 효율의 문제에 공부를 무한정으로 해도 100점을 초과 할 수 없으므로

100에서 현재 점수를 뺀 점수가 오르는 수치보다 작다면 plus배열의 자신의 값을 100 - 현재점수로 변경한다.

이후 오르는 점수를 음수로 바꿔 힙에 저장 후 heappop -> 100 - 현재점수 확인 -> heappush 사이클을 주어진 시간동안 반복한다. 

음수로 바꾸는 이유는 맥스 힙을 이용하기 위해서이다. 

 

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


n, m = map(int,input().split())
n *= 24
score = list(map(int,input().split()))
plus = list(map(int,input().split()))
heap = []
for i in range(m):
    if score[i] + plus[i] > 100:
        plus[i] = 100 - score[i]
    heappush(heap,[-plus[i], score[i]])

time = 0
while time < n:
    p, s = heappop(heap)
    s -= p
    if s - p > 100:
        p = s - 100
    heappush(heap, [p, s])
    time += 1
answer = 0
for i in range(m):
    answer += heap[i][1]
print(answer)