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

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

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

---

• 문제 : 

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

 

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

 

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

 

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

 

 

 

---

• 풀이 :

우선순위 큐를 사용한 그리디 문제였습니다.

 

알고리즘의 흐름은 다음과 같습니다.

 

1. 공부하는 시간당 상승하는 점수인 bi를 기준으로 최대 힙을 구성합니다.

 

2. 최대 힙의 요소마다 공부할 수 있는 남은 시간과, 해당 과목을 최대 점수로 만드는 데 필요한 시간을 계산하여 두 가지 경우로 나눠줍니다.

 

- CASE 1 : 남은 시간동안 공부하여 해당 과목의 최대점을 맞을 수 있는 경우

    해당 과목이 최대 몇 점 맞을 수 잇는지 계산하고 점수가 100점이라면 answer에 더합니다. 100점이 아니라면 bi값을  (100 - 최대점수)로 변경하여 다시 최대힙에 삽입합니다.

 

- CASE 2 : 남은 시간동안 공부해도 최대점을 못 받는 경우

    남은 시간 x bi값을 하여 a에 더해주고 answer에 값을 더해줍니다.

 

 

3. 공부를 하나도 할 수 없는 과목이 존재할 수 있으므로 heap의 모든 a값을 answer에 더해줍니다.

 

4. 모든 과목을 100점 맞을 수 있는 경우가 있으므로 heap이 비게 된다면 반복문을 종료합니다.

 

 

 

 

---

• 소스코드 : 

import sys
import heapq as hq
input = sys.stdin.readline


N, M = map(int,input().split())
score = list(map(int,input().split()))
up_score = list(map(int,input().split()))
time = 0
heap = []
answer = 0
for i in range(M):
    hq.heappush(heap,[-up_score[i],score[i]])
while 24*N > time and heap:
    b, a = hq.heappop(heap)
    if (100-a)//(-b) < 24*N - time:
        tmp = a + (-b * ((100-a)//(-b)))
        if tmp == 100:
            answer += 100
        else:
            hq.heappush(heap,[-(100 - tmp), tmp])
        time += (100-a)//(-b)
    else:
        answer += a + (24*N - time) * (-b)
        time += (24*N - time)
for b, a in heap:
    answer += a
print(answer)