[백준][그리디] 13904. 과제

13904. 과제

 

 

• 내 풀이
  • 1일차, 2일차 ...k일차... n일차 까지 dp처럼 최적의 값을 구하려면 어떻게 해야할 지 고민함.
  • k일차 까지 중에 가능한 과제 중 가장 합리적인 것을 선택해야함
  • 하루에 하나만 수행할 수 있으므로 k일차까지는 k개의 과제만 가능
    • → 1일차에는 1개, 2일차에는 2개...5일차에는 5개
    • for문이 진행되면서 i개 까지만 담을 수 있는 리스트를 가진다고 가정하고
    • 매번 새로운 과제가 들어오면 리스트 값에서 가장 작은 값과 비교해서 큰 값으로 저장
      • 이 때, heap을 사용하면 최솟값을 바로 꺼낼 수 있음

import heapq
n = int(input())
lst = [[] for _ in range(1001)]
for i in range(n):
    d, w = map(int, input().split())
    lst[d].append(w)

result = []
for i in range(1001):
    for j in lst[i]:
        if len(result) < i:
            heapq.heappush(result, j)
        else:
            minV = heapq.heappop(result)
            heapq.heappush(result, max(minV, j))

print(sum(result))

 

 

• 다른 사람 풀이
  
  • 이런 문제는 뒤에서 부터 확인해서 푸는게 좋음
  • 가장 마지막날부터 그날 할 수 있는 과제들 중 가장 최적의 과제를 선택하고
    • 나머지 과제들은 리스트에 넣어둠
    • 이후 진행하면서 새로운 과제+리스트에남은 과제 중 최적의 값으로 하루에 하나씩 선택해 나가는 것