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

문제

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

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

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

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

 

입력

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

둘째 줄에는 정수 a_1, a_2, ..., a_M이 공백으로 구분되어 주어진다.

셋째 줄에는 정수 b_1, b_2, ..., b_M이 공백으로 구분되어 주어진다.

 

출력

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

 

제한

1 <= N, M <= 200,000

1 <= a_i, b_i <= 100

 

내가 쓴 코드 1 (틀림)

from sys import stdin; input = stdin.readline
# N x 24 : 공부 가능 시간, M : 시험 과목 수
N, M = map(int, input().split())
# 기본 점수
basic_scores = list(map(int, input().split()))
# 공부 1시간 당 올릴 수 있는 점수
get_scores = list(map(int, input().split()))

# 한 과목 당 최대 100점
# 최종 성적 최댓값 구하기 (최종 성적은 모든 과목 성적 합)

# 공부 가능 시간
study_time = N * 24
scores = [(x, y, z) for x, y, z in zip([i for i in range(M)], basic_scores, get_scores)]
scores.sort(key=lambda x: x[2], reverse=True)

SUM = 0     # 성적 합
lack = []
for score in scores:
    temp = score[1]
    while temp <= 100 - score[2] and study_time > 0:
        temp += score[2]
        study_time -= 1
        if lack and study_time:
            if 100 - lack[0][1] > score[2]:
                SUM += 100 - lack[0][1]
                study_time -= 1
                lack.pop(0)
    if temp >= 100:
        temp = 100
    else:
        lack.append([score[0], temp])
    SUM += temp

while lack and study_time > 0:
    SUM += 100 - lack[0][1]
    study_time -= 1
    lack.pop(0)

print(SUM)

 

내가 쓴 코드 2 (맞.)

from sys import stdin; input = stdin.readline
N, M = map(int, input().split())
basic_score = list(map(int, input().split()))
get_scores = list(map(int, input().split()))
study_time = N * 24

score_time = []     # [시간당 점수, 시간]
for i in range(M):
    time = (100 - basic_score[i]) // get_scores[i]
    rem_score = (100 - basic_score[i]) % get_scores[i]
    # time 이라는 시간에, 한 시간 공부 당 얻는 점수
    score_time.append([get_scores[i], time])
    if rem_score:
        # 1시간에, 얻는 점수
        score_time.append([rem_score, 1])

score_time.sort(reverse=True)
sum_score = sum(basic_score)
# score : 시간당 점수, time : 시간
for score, time in score_time:
    if study_time > 0:
        sum_score += score * min(time, study_time)
        study_time -= min(time, study_time)
print(sum_score)

이 문제는 우선순위큐를 위한 문제인 것 같은데 정말 잘 몰라서,, 그렇게 풀 순 없었다. 결국 우리 반 사람의 도움으로 우선순위큐를 사용하지 않은 코드로 해결할 수 있었다. 근데 정말 위의 내가 쓴 코드 1 은 왜 틀린지 너무너무 모르겠당... 웬만한 반례도 다 정답이 잘 나오는데... 너무 어려웡 ㅠㅜ,, 나에게 왜 이런 시련을 주시나용.... 흑흐궁

두번째 코드의 첫번째 for문은 나도 어느정도 생각했던 부분이라 잘 알겠는데, 두번째 for문이 또 잘 이해가 안됐다... 그래서 미량이한테도 몇번이나 물어보공... 어려워효.....!ㅠㅠㅠㅠ 그래두 지금은 잘 이해했다! 근데 이런 비슷한 다른 문제 풀라하면 못 풀수도 있....ㅎㅎㅎㅎ^^;

 

제출 결과