[백준] 13904번 : 과제

13904번: 과제

13904번: 과제

🤔 문제분석

서로소 집합, 우선순위 큐 두가지로 문제를 해결하였다. 서로소 집합으로 문제를 해결할때에는 과제의 가중치를 기준으로 내림차순 정렬하였고, 우선순위큐는 과제 걸리는 시간 기준으로 오름차순 정렬하여 문제를 해결 하였다.

서로소 집합 문제는 과제를 완료한뒤에, 현재 날짜와 현재 날짜 -1 를 유니온하여, 다음 리터레이션에서 현재날짜를 파인드 하였을때 0이게 된다면 과제를 할 수 없는 상황임으로 과제를 해결 할 수 없는 상황이다. 그 상황을 제외하고는 과제를 해결 할 수 있으므로 정답 가중치에 과제 가중치를 더한다.

우선순위 큐 문제는 걸리는 시간을 기준으로 정렬을 하였기때문에 현재 시간에서 가장 높은 가중치를 선택해야한다. 예를들어 (1, 5), (1, 10)이 있을때에는 10을 선택해야한다.

💻 코드

서로소 집합

import sys
input = sys.stdin.readline
N = int(input())

works = []
for _ in range(N):
    day, cost = map(int, input().split())
    works.append((day, cost))
    
works.sort(key=lambda x:-x[1])

parent = [i for i in range(10001)]

def find(v1):
    if v1 != parent[v1]:
        parent[v1] = find(parent[v1])
        return parent[v1]
    
    return v1

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

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

print(ans)

우선순위 큐

import sys
import heapq

input = sys.stdin.readline
N = int(input())

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

works.sort()

queue = []
for day, cost in works:
    heapq.heappush(queue, (cost))
    
    while len(queue) > day:
        heapq.heappop(queue)
        
print(sum(queue))

🎯 피드백 및 개선사항

예전에 공항이라는 문제를 해결할때에 통찰력을 얻어서 서로소 집합으로 문제를 해결 할 수 있었다.