[BOJ] 파이썬 13904번_과제

문제링크 : https://www.acmicpc.net/problem/13904

풀이

1. 그리디

    import heapq
    import sys
    input = lambda:sys.stdin.readline().strip()
   
    n = int(input())
   
    tareas = []
    times = set()
    for _ in range(n):
        t, value = map(int, input().split())
        tareas.append((t,value))
        times.add(t)
    tareas.sort(key = lambda x: (x[0],x[1]))
    times = list(times)
    times.sort(reverse=True)
   
    cand = []
    ans = 0
    for time in range(max(times), 0, -1):
   
        while tareas and tareas[-1][0] == time:
            tarea = tareas.pop()
            heapq.heappush(cand, (-tarea[1], tarea[1] ))
   
        if cand:
            ans += heapq.heappop(cand)[1]
   
    print(ans)
   

거꾸로 생각하면 해결할 수 있는 문제다. 우선 마감일이 많이남은 순, 가치가 높은 순 으로 과제들을 정렬한다.

이후 마감일의 거꾸로, (마감일 큰 -> 작은) 마감일 만큼 반복한다.

-  해당하는 마감일의 과제들을 모두 우선순위 큐에 넣어준다.
- 우선순위 큐에서 가장 가치가 높은 과제를 꺼낸다. 이때 꺼낸 과제가 해당 마감일에 수행할 과제이다.

이런식으로 모든 날에 수행할 과제를 그리디로 선택하면 해결된다.

1. 유니온 파인드

import sys
input = lambda:sys.stdin.readline().strip()
n = int(input())

tareas = []
times = []
for _ in range(n):
    t, value = map(int, input().split())
    tareas.append((t,value))
    times.append(t)


roots = [i for i in range(max(times) + 1)]
schedule = [-1 for _ in range(max(times) + 1)]

tareas.sort(key=  lambda x: x[1], reverse= True)

def find(x):
    if x == roots[x]:
        return x

    roots[x] = find(roots[x])
    return roots[x]

def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    roots[x] = y


for tarea in tareas:
    t, cost = tarea
    day = find(t)
    if schedule[day] == -1:
        schedule[day] = cost
    if day - 1 > 0:
        union(day,day - 1)

ans = 0
for val in schedule:
    if val != -1:
        ans += val

print(ans)

이 문제가 유니온 파인드로 풀린다는 것이 놀라웠다. 생각하기 힘든 풀이

핵심 아이디어는 두개다.

• 가치가 높은 과제는 우선적으로 처리한다. -> 단순 정렬
• 마감기한이 같은 다른 과제가 존재한다면 그전에 끝내게 한다. -> 서로소집합으로해결

우선 과제를 가치 순으로 정렬한다. 어쨋거나 높은 가치를 지닌 과제들은 순서가 어떻든 수행되어야 하기 떄문이다.

문제는 날짜들이다. 이 날짜들을 해결하기 위해 유니온 파인드 알고리즘, 서로소 집합을 사용한다.

수행 과정은 다음과 같다.

각 마감일에 과제가 할당되지 않았다면 할당한다 이후 전 날과 union한다.

이후 할당된 마감일의 과제가 들어온다면 전날쪽의 서로소집합과 union되었으므로 그 이전 어딘가의 날에 비어있는 곳에 할당될 것이다,

이걸 반복한다.

icpc 캠프에서 배운 풀이다. 생각하기 힘든 풀이였고 유니온파인드를 다양한 상황에서도 고려할 수 있다는 사실을 배웠다.

Reference

icpc sinchon 2022 winter algorithm camp.