1781 - 컵라면 [그리디]

출처 : 백준_1781_컵라면

문제

Deadline안에 최대한 많은 컵라면을 받을 수 있는 문제를 푼는 것이 목표이다.

우선순위 큐(가장 작은 값을 pop하는 자료구조)로 구현을 해야 한다. 일단 주어진 리스트를 끝나는 시간이 빠른 순으로 정렬해야 한다. 한번에 하나의 문제만 풀 수 있기 때문에 마감기한이 큐보다 크면 같은 마감기한이어도 큐에 추가를 한다. 하지만, 큐의 길이가 마감기한보다 크면 그 안에서 가장 작은 값을 pop해서 없애버린다. 이런 방향으로 전체 리스트를 흝다보면 마감기한내에 가장 많은 컵라면을 얻을 수 있다.

해당 문제는 Python3으로 제출했을 시간초과가 떴다. 그래서, Pypy3으로 했더니 맞았다. Python3으로 해당 문제를 푼 사람이 없는 것으로 보아……Python3으로는 시간초과가 날 수 밖에 없는 것 같다.

풀이