[백준/Python] 2109번(그리디)_순회강연

📌문제 유형

그리디, 정렬(골드 Lv.4)

 

📌문제

 

2109번: 순회강연

 

 

📌나의 문제풀이

- (실패)

n = int(input())

list_ = []
for _ in range(n):
    list_.append(list(map(int,input().split())))

list_.sort(key = lambda x:[x[1], -x[0]])
# print(list_)

result = 0
if len(list_) > 0:
    result = list_[0][0]
    day = 1
    for i in range(1, len(list_)):
        if day == list_[i][1]:
            continue
        elif day < list_[i][1]:
            day = list_[i][1]
            result += list_[i][0]
        else:
            day = list_[i][1]
        day += 1

print(result)

 

 

📌다른사람의 문제 풀이

- 우선순위 큐 사용

import heapq

n=int(input())
lst=[]

for i in range(n):
  lst.append(list(map(int, input().split())))

lst.sort(key=lambda x: (x[1]))
p_list=[]
for i in lst:
  heapq.heappush(p_list, i[0])
  if (len(p_list)>i[1]):
    heapq.heappop(p_list)

print(sum(p_list))

 

- DP 이용

n = int(input())
dp = [0] * (10001)
memo = []

for _ in range(n):
    p,d = map(int,input().split())
    memo.append((p,d))

memo.sort(key=lambda x : (-x[0],x[1]))

for i in range(n):
    np, nd = memo[i][0], memo[i][1]
    for j in range(nd ,0, -1):
        if dp[j] == 0:
            dp[j] = np
            break
print(sum(dp))

 

📌리뷰

- 이전 날짜에도 순회할 수 있음! 핵심은 순회할 곳 날짜 비교하는 것