테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 연료 채우기 ======

===== 풀이 =====
  * 소위 [[ps:그리디#주유소 문제]]의 변형. 주유소마다 판매 가격이 다른게 아니라, 판매량이 다르고 목표는 주유소 방문 횟수를 최소화하는것.
  * 기본 접근 방법은 [[ps:그리디#주유소 문제]]와 같다. 주유소를 들를지 말지를 주유소 방문 시점에 결정하려는 생각을 버리고, 지금은 그냥 지난 다음에, 나중에 기름이 부족해지면 아까 주유소를 들렀던걸로 처리하는 것. 지나온 주유소들 중에서 가장 판매하는 양이 많은 주유소에서 샀던걸로 처리해야 하므로, 지나온 주유소들을 최대힙으로 관리하면 된다. 
  * 입력 데이터에 주유소들이 정렬되지 않았다는 것이 주의하자.
  * 주유소들을 정렬하는데에 O(nlogn), n개의 주유소들에 대해서 각각 최대 한번의 heappush, heappop 연산이 필요하므로 여기에도 O(nlogn)이 걸린다. 그러므로 총 시간복잡도는 O(nlogn)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1826. 연료 채우기".

- Problem link: https://www.acmicpc.net/problem/1826
- Solution link: http://www.teferi.net/ps/problems/boj/1826

Tags: [Greedy]
"""

import heapq
import sys

INF = float('inf')


def main():
    N = int(sys.stdin.readline())
    stations = []
    for _ in range(N):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        stations.append((a, b))
    L, P = [int(x) for x in sys.stdin.readline().split()]

    heap = []
    answer = 0
    movable_dist = P
    stations.append((L, INF))
    for dist, fuel in sorted(stations):
        while heap and movable_dist < dist:
            movable_dist += -heapq.heappop(heap)
            answer += 1
        if movable_dist < dist:
            print('-1')
            break
        heapq.heappush(heap, -fuel)
    else:
        print(answer)


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}