[Python] 백준 2109 순회강연

🧑‍💻 [Python] 백준 2109 순회강연

Gold 3 - 힙

null

강연을 하는데, 각 강연마다 강연료와 몇 일 안에 강연을 하는지 입력을 받는다

최대한 강연료를 많이 받을 수 있도록 코드를 짜야 한다

 

 

문제풀이 1

• 힙 리스트 안에, 강연료 기준으로 최대 힙으로 넣는다
  • 즉 튜플 형태로 힘 리스트에 넣는 것
• 그리고 힙을 하나씩 빼면서, 강연을 해야하는 날이, False이면 True로 바꾼다
  • 강연을 해야 하는 날이, True일 경우, 그 전날을 본다.
  • 이것을 False를 찾을 때 까지 뒤로 탐색을 한다
  • 만약 1일차까지 다 True일 경우는, 그 강연은 못 하는 것이다

 

문제풀이 2

• 일단 강의 날짜 기준으로 오름차순으로 정렬을 한다
• 그리고 강연료를 힙 안에 넣어준다
  • 힙의 길이는 날짜와 같거나, 적어야 한다
  • 넣었는데, 날짜보다 힙의 길이가 더 길면, heappop을 한다
    • 어차피 제일 작은 강연료를 빼는 것
  • 즉 2일까지 강연을 해야 하면, 힙 안에는 원소가 2개가 있어야 한다

---

 

코드

import heapq

N = int(input())

days = [False] * 10001
lecture = []
answer = 0

for _ in range(N):
    temp_wage, temp_time = map(int, input().split())
    heapq.heappush(lecture, (-temp_wage, temp_time))

while lecture:
    wage, time = heapq.heappop(lecture)

    if days[time] == False:
        days[time] = True
        answer += wage
    else:
        time -= 1
        while time > 0:
            if days[time] == False:
                days[time] = True
                answer += wage
                break
            else:
                time -= 1

print(-answer)

---

 

코드 2

import heapq

N = int(input())

schedule = []

for _ in range(N):
    money, day = map(int, input().split())
    schedule.append((day, money))

schedule.sort(key=lambda x : x[0])

heap = []

for time, pay in schedule:
    heapq.heappush(heap, pay)

    if len(heap) > time:
        heapq.heappop(heap)

print(sum(heap))