백준 13904 과제 파이썬 풀이

난이도 : 골드3

풀이일 : 2403192

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

13904번: 과제

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys, heapq

N = int(sys.stdin.readline())
queue = []  # 마감일 우선 과제 정보 정렬
total = []  # 점수 낮은순 정렬

for _ in range(N):
    limit, score = map(int, sys.stdin.readline().split())
    heapq.heappush(queue, (limit, score))

while queue:
    limit, score = heapq.heappop(queue)
    # 마감일 내에 할 수 있는 일이라면 추가
    if len(total) < limit:
        heapq.heappush(total, score)
    # 마감일까지 과제 일정이 차있는 경우, 제일 낮은 점수와 비교 후 교체
    else:
        if total[0] < score:
            heapq.heappop(total)
            heapq.heappush(total, score)

print(sum(total))

 

heapq를 사용해 우선순위 큐를 구현하여 풀이하였다.

• 마감일을 기준으로 과제의 정보를 정렬해 queue에 추가한다.
• queue 내부에 요소가 존재한다면 아래 과정을 반복한다.
• 마감일, 점수 정보를 마감일이 조금 남은 순서대로 queue에서 뽑아내기
• 현재 total에 들어있는 과제 점수의 수가 마감일보다 적다면, 과제를 수행할 일정이 충분하기 때문에 바로 점수를 total에 추가한다.
  • 이때, total도 heapq를 사용하여 과제 점수가 낮은 순서로 정렬되도록 한다.
• 현재 total에 들어있는 과제 점수의 수가 마감일보다 적지 않다면, total의 점수 중 가장 작은 점수와 현재 점수를 비교한다.
  • total의 가장 작은 수보다 현재 점수가 작다면, total을 수정하지 않고 넘어간다.
  • total의 가장 작은 수보다 현재 점수가 크다면, total의 가장 작은 수를 제거하고 현재 점수를 total에 추가한다.
• total에 있는 모든 과제 점수를 합산하여 출력한다.

---

느낀점

• 처음에는 dp로 접근해봤었는데, 잘 되지 않아 수정했다. 배낭 알고리즘처럼 풀려고 했었는데 덜 익숙한 방식이라 안되는가 싶었더니 그냥 더 편하고 익숙한 방법이 있었네 싶었다.
• 코드부터 치지 말고 충분히 생각한 다음 로직을 설계해서 치는 습관을 들여야지