백준 1781. 컵라면

https://www.acmicpc.net/problem/1781

1781번: 컵라면

 

쉽지 않은 문제였는데, 이해하고 나면 원리는 간단하다.

pair<데드라인, 컵라면>형을 담는 pair.second 기준 min heap 우선순위 큐를 이용한다. (즉 컵라면 기준 min heap)

 

우선 주어지는 문제들을 데드라인 기준 오름차순 정렬해서 데드라인이 작은 문제부터 탐색한다.

데드라인이 현재 일수 보다 크거나 같으면 우선 우선순위 큐에 담고 일수를 1 늘린다.

이렇게 일들을 우선순위 큐에 담다가 데드라인이 현재 일수보다 작은 일을 만나면 우선순위 큐에 있는 내가 하기로 한 일들 중 top에 있는 컵라면을 가장 적게 주는 일을 빼고 담으면 된다. 

 

이렇게 모든 일들을 순회하면 결국 우선순위 큐에는 최대 갯수의 컵라면을 얻을수 있는 일들로 차있으므로 모두 빼면서 컵라면 수를 카운트하면 된다. 

 

 

참고하면 좋은 테스트 케이스 : 

9

1 14

1 7

2 10

2 5

3 8

4 18

4 12

4 6

5 5