기간 제한이 있는 과제들에서 최대 가치를 얻는 그리디 알고리즘

13904번: 과제 (acmicpc.net)

 

과제의 기간 제한이 있고 해당 과제를 수행했을 때 얻는 가치가 서로 다르다

 

하루에 하나씩 과제만 처리할 수 있다.

 

주어진 과제들을 적절히 처리해서 최대 가치를 구한다면?

 

---------------------------------------------------------------------------------------------------------------------------

 

처음에는 과제 점수가 높은 순서대로 내림차순 정렬해서

 

현재 날짜랑 비교해서 처리할 수 있는 과제면 일단 가져가고

 

날짜랑 비교했을 때 처리할 수 없는 과제면.. 지금까지 가져간 과제들 비교해서... 실제 처리할 수 있는지 체크해보는것?

 

4 60

4 40

1 20

2 50

3 30

4 10

6 5

 

얘를 정렬하면

 

4 60

2 50

4 40

3 30

1 20

4 10

6 5

 

1일차에 4 60 

 

2일차에 2 50

 

3일차에 4 40

 

4일차에 3 30을 가져가야하는데 3일내로 끝냈어야하니 못먹는건데

 

4 60, 2 50, 4 40에 대해서 2 50, 3 30, 4 40, 4 60 순으로 처리하면 처리할 수 있는 과제니까 가져가고..

 

이러면 1 20, 4 10은 못가져가니 6 5를 가져가면 총 185

 

이런 느낌으로 생각해서 억지로? 구현해봤는데 안되더라

 

------------------------------------------------------------------------------------------------------------------------------------ 

 

다른 방법으로 기간 제한이 빠른 순으로 오름차순 정렬

 

1 20

2 50

3 30

4 10

4 40

4 60

6 5

 

 

그래서 일단 빨리 끝내야하는 과제를 일단 가져가고...

 

1 20, 2 50, 3 30, 4 10

 

4 40을 가져가야하는데 현재 처리한 과제가 4개 있으므로 얘는 가져갈 수가 없다

 

그러면 1 20, 2 50, 3 30, 4 10 중에서 점수가 가장 작은 4 10을 버리고 4 40을 가져가는게 유리하겠지

 

당연하지만

 

1 50 2 50 3 50 4 50 

 

이렇게 들어가있는데 4 40을 넣어야한다고 해서 점수가 가장 작은 4 50을 빼고 4 40을 넣는 것은 안해야겠지

 

근데 애초에 이 상황은 나올수가 없긴하다

 

배열에 (1,20), (2,50), ... 튜플로 들어가는데 첫번째 원소로 오름차순 정렬하면,

 

첫번째 원소가 같으면 두번째 원소 기준으로 오름차순 정렬하니까 

 

다음에 들어오는 원소의 점수 값이, 같은 기간제한이라면 무조건 크게된다

 

--------------------------------------------------------------------------------------------------------------------------------------------

 

뭐 어쨌든 중요한건 기간 제한이 빠른 순으로 오름차순 정렬하고, 일단 과제를 수행하면서...

 

기간 제한이 다 차서 수행할 수 없는 과제가 있다면, 현재 수행한 과제 중 점수가 가장 작은걸 빼고, 이 과제를 넣어준다

 

여기서 "현재 수행한 과제 중 점수가 가장 작은걸 빼는것"은 우선순위 큐를 이용해서 로그 시간에 찾을 수 있다

 

#기간 제한이 있는 과제들을 적절하게 수행해서 최대 가치를 얻는 방법
import heapq
from sys import stdin

n = int(stdin.readline())

A = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())
    A.append((x,y))

#기간 제한이 빠른 순으로 오름차순 정렬
A.sort()

queue = []

for x,y in A:
    
    #일단 과제를 계속 수행하면서
    heapq.heappush(queue,y)
    
    #수행한 과제수(현재 날짜)가 현재 과제를 처리해야하는 제한보다 많아지면?
    #수행한 과제들 중 점수가 가장 작은걸 제거
    if len(queue) > x:
        
        heapq.heappop(queue)

#끝나면 큐에 남아있는 점수 합이 최댓값
total = sum(queue)

print(total)

 

 

일단 큐에 계속 넣어서, 현재 처리해야하는 기간 제한보다 큐의 길이가 커지면, 큐에서 제거하는 방법 말고도

 

현재 큐의 길이가 처리해야하는 기간제한과 같다면, 현재 큐에서 가장 점수가 작은걸 제거하고 큐에 집어넣어도 똑같다

 

for x,y in A:
    
    if len(queue) == x:
        
        heapq.heappop(queue)
        
    heapq.heappush(queue,y)

 

 

 

똑같은 문제

 

1781번: 컵라면 (acmicpc.net)

 

2109번: 순회강연 (acmicpc.net)