[백준] 2109번 : 순회강연

2109번: 순회강연

2109번: 순회강연

🤔 문제분석

두가지의 방식으로 문제를 풀어보았습니다. 처음에 제가 풀은 방식은 유니온-파인드를 응용하여 문제를 해결하였고, 정답 판정을 받은뒤에 다른사람은 어떻게 풀었을까 풀이를 참조해보니, 우선순위큐를 활용하여 문제를 해결하신분이 있어서 풀이를 참조하였습니다.

유니온-파인드

유니온-파인으로 문제를 해결할때에는 정렬을 p의 내림차순을 정렬한뒤에 순회합니다.

• 파인드 : 문제에서 이야기한 d일안에 강연을 만족하기위해서는 파인드 하였을때 노드의값이 0보다 커야합니다.
• 유니온 : 만약 파인드했을때의 날짜가 0보다 크다면 해당 날짜를 **(d-1)**과 유니온을 해줍니다.

우선순위 큐

우선순위 큐로 문제를 해결할때에는 정렬을 d의 오름차순으로 정렬한뒤 순회합니다. 순회할때 큐에 넣고 현재 날짜보다 큐가 클경우 heappop을 함으로서 가장 낮은 가중치의 값을 pop 시킵니다.

💻 코드

유니온-파인드

import sys
input = sys.stdin.readline

N = int(input())
cost = []
for _ in range(N):
    p, d  = map(int, input().split())
    cost.append((p, d))

cost.sort(key=lambda x:(-x[0]))
parent = [i for i in range(10001)]

def find(p1):
    if p1 != parent[p1]:
        parent[p1] = find(parent[p1])
        return parent[p1]
    
    return p1
    
def union(p1, p2):
    v1 = find(p1)
    v2 = find(p2)
    if v1 != v2:
        if v1 > v2:
            parent[v1] = v2
        else:
            parent[v2] = v1

ans = 0
for p, d in cost:
    day = find(d)
    if day > 0:
        union(day, day-1)
        ans += p

print(ans)

우선순위 큐

import sys
from heapq import heappop, heappush

input = sys.stdin.readline

N = int(input())
cost = []
for _ in range(N):
    p, d  = map(int, input().split())
    cost.append((p, d))
    
cost.sort(key=lambda x:(x[1]))
q = []
for p, d in cost:
    heappush(q, p)
    
    while len(q) > d:
        heappop(q)

print(sum(q))

🎯 피드백 및 개선사항

정답을 판정받은뒤에 다른사람들의 풀이를 참조하니, 유니온-파인드로 문제를 해결한 사람은 저 밖에 없어서 기분이 좋았습니다. 알고리즘의 매력은 이런곳에서 느끼는거 아니겠습니까 👏👏👏