240406 [BOJ/백준] 23254. 나는 기말고사형 인간이야

 

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

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

---

나의 코드

1. 현조코드보고 다시 풀어봄(성공)

import sys

n, m = map(int, sys.stdin.readline().split())
base_score = list(map(int, sys.stdin.readline().split()))
plus_score = list(map(int, sys.stdin.readline().split()))

total_time = 24 * n  # 총 공부시간
plus_list = []
for i in range(m):
    study_time = (100-base_score[i]) // plus_score[i] # 공부시간
    plus_list.append((plus_score[i], study_time))  # 추가점수와 공부시간
    plus_list.append((((100-base_score[i]) % plus_score[i]), 1)) # 나머지추가점수와 1시간

ans = sum(base_score)  # 기본점수의 합
plus_list.sort(reverse=True)  # 추가점수가 큰 값부터 내림차순으로 정렬
for i in range(len(plus_list)):
    ans += plus_list[i][0] * min(plus_list[i][1], total_time)  # 추가점수 계산
    total_time -= min(plus_list[i][1], total_time)  # 계산한만큼 총 공부시간에서 공부시간 빼준 값 재할당

print(ans)

 

2. 내가 처음 시도한 코드(틀림)

from collections import deque
import sys

N, M = map(int, sys.stdin.readline().split())
score = deque()
base_score = list(map(int, sys.stdin.readline().split()))
plus_score = list(map(int, sys.stdin.readline().split()))
for i in range(M):
    score.append((base_score[i], plus_score[i]))

total_time = 24*N
ans = 0
while score and total_time > 0:  # 구해야 할 점수와 공부할 시간이 남아있다면
    max_v = 0
    for i in range(len(score)):
        if max_v < score[i][1]:
            max_v = score[i][1]
    a, b = score.popleft()
    if b != max_v:
        score.append((a, b))
    else:  # b==max_v:
        study_time = round((100 - a) / b)
        if study_time == 0:
            ans = a + b
            if ans >= 100:
                ans = 100
                break
        if study_time > total_time:  # 남은 시간이 공부할 수 있는 시간보다 적다면
            study_time = total_time  # 남은 시간을 공부시간에다 넣는다.
        total_time -= study_time
        total_plus_score = a + (b * study_time)
        if total_plus_score >= 100:
            total_plus_score = 100
        ans += total_plus_score
while score:
    a, b = score.popleft()
    ans += a
print(ans)

결과

---

처음에 우선순위 큐가 뭔지 모르고 그냥 냅다 큐에다가 넣어서 추가점수의 최댓값을 구했다. 그리고 큐에서 빼면서 최댓값이랑 같을 때의 점수와 시간을 구해서 뺐다. 주어진 입력값과 질문 게시판에 있는 코드들의 결과가 다 나왔으나 틀린코드였는데 아마도 주어진 반례들에만 맞게끔 하드코딩을 했던게 원인일 것 같다.

인터넷에는 힙을 쓴 풀이방법들만 올라왔지만 내가 생각한 방법에 벗어나지 않게 풀어보고 싶었다. 그렇게 구현한 친구가 있어서 그 코드를 보고 다시 풀어봤다. 그렇게 해서 성공했고 조만간 힙으로도 푼 방식을 보고 익혀서 다시 풀어봐야겠다.